给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。

比如两个串为：

abcicba

abdkscab

ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。

收起

输入

第1行：字符串A第2行：字符串B(A,B的长度 <= 1000)

输出

输出最长的子序列，如果有多个，随意输出1个。

输入样例

abcicbaabdkscab

输出样例

abca

思路就是先求最长公共子序列，然后再根据路径逆推，找到匹配点。

#include<iostream>#include<queue>#include<algorithm>#include<set>#include<cmath>#include<vector>#include<map>#include<stack>#include<bitset>#include<cstdio>#include<cstring>//---------------------------------Sexy operation--------------------------//#define cini(n) scanf("%d",&n)#define cinl(n) scanf("%lld",&n)#define cinc(n) scanf("%c",&n)#define cins(s) scanf("%s",s)#define coui(n) printf("%d",n)#define couc(n) printf("%c",n)#define coul(n) printf("%lld",n)#define speed ios_base::sync_with_stdio(0)#define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)//-------------------------------Actual option------------------------------//#define Swap(a,b) a^=b^=a^=b#define Max(a,b) a>b?a:b#define Min(a,b) a<b?a:b#define mem(n,x) memset(n,x,sizeof(n))#define mp(a,b) make_pair(a,b)//--------------------------------constant----------------------------------//#define INF 0x3f3f3f3f#define maxn 1005#define esp 1e-9using namespace std;typedef long long ll;typedef pair<int,int> PII;//------------------------------Dividing Line--------------------------------//string a,b,ans;int dp[maxn][maxn];int main(){ans.clear();cin>>a>>b;a=' '+a;b=' '+b;int la=a.size();int lb=b.size();for(int i=1;i<la;i++){for(int j=1;j<lb;j++){if(a[i]==b[j])dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}int m=la-1,n=lb-1;while(dp[m][n]){if(dp[m][n]==dp[m-1][n]) m--;else if(dp[m][n-1]==dp[m][n]) n--;else{if(a[m]!=' ')ans=a[m]+ans;m--,n--;}}cout<<ans<<endl;}