C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 1006 最长公共子序列Lcs

给出两个字符串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 }```
  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/56788/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!