给出两个字符串A B,求A与B的最长公共子序列(子序列不要求是连续的)。
比如两个串为:
abcicba
abdkscab
ab是两个串的子序列,abc也是,abca也是,其中abca是这两个字符串最长的子序列。
输入
第1行:字符串A
第2行:字符串B
(A,B的长度 <= 1000)
输出
输出最长的子序列,如果有多个,随意输出1个。
输入样例
abcicba
abdkscab
输出样例
abca
```
1 #include<cstdio>
2 #include<iostream>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 char a[1020],b[1020];
7 int f[1020][1020];
8 int ans[1020][1020];
9 void dfs(int x,int y){
10 if(x==0||y==0) return;
11 if(ans[x][y]==0){
12 dfs(x-1,y-1);
13 cout<<b[y];
14 }
15 else if(ans[x][y]==1){
16 dfs(x-1,y);
17 }
18 else{
19 dfs(x,y-1);
20 }
21 }
22 int main(){
23 cin>>a>>b;
24 int l1=strlen(a),l2=strlen(b);
25 for(int i=l1;i>=1;i--) a[i]=a[i-1];
26 for(int i=l2;i>=1;i--) b[i]=b[i-1];
27 for(int i=1;i<=l1;i++){
28 for(int j=1;j<=l2;j++){
29 if(a[i]==b[j]){
30 f[i][j]=f[i-1][j-1]+1;
31 ans[i][j]=0;
32 }
33 else if(f[i-1][j]>=f[i][j-1]){
34 f[i][j]=f[i-1][j];
35 ans[i][j]=1;
36 }
37 else{
38 f[i][j]=f[i][j-1];
39 ans[i][j]=-1;
40 }
41 }
42 }
43 //cout<<f[l1][l2];
44 dfs(l1,l2);
45 return 0;
46 }```