首页 > 代码库 > 1006 最长公共子序列Lcs

1006 最长公共子序列Lcs

2024-11-28 09:24:39   203人阅读

 
基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题
 
给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。
 
比如两个串为：
 
abcicba
abdkscab
 
ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。
Input
第1行：字符串A第2行：字符串B(A,B的长度 <= 1000)
Output
输出最长的子序列，如果有多个，随意输出1个。
Input示例
abcicbaabdkscab
Output示例
abca

技术分享
 1 /* 2     记录一下dp是怎么走的  3     最后再dfs走回去  4 */ 5 #include <ctype.h> 6 #include <cstdio> 7 #include <cstring> 8  9 const int MAXN=1010;10 11 char s1[MAXN],s2[MAXN];12 13 int f[MAXN][MAXN],pre[MAXN][MAXN];14 15 inline void read(int&x) {16     register char c=getchar();17     for(x=0;!isdigit(c);c=getchar());18     for(;isdigit(c);x=x*10+c-48,c=getchar());19 }20 21 inline int max(int x,int y) {22     return x<y?y:x;23 }24 25 void dfs(int len1,int len2) {26     if(len1==0||len2==0) return;27     if(pre[len1][len2]==1) {28         dfs(len1-1,len2-1);29         printf("%c",s1[len1]);30     }31     else if(pre[len1][len2]==2) dfs(len1-1,len2);32     else dfs(len1,len2-1);33 }34 35 int main() {36     scanf("%s%s",s1+1,s2+1);37     int l1=strlen(s1+1),l2=strlen(s2+1);38     for(int i=1;i<=l1;++i)39       for(int j=1;j<=l2;++j) {40           if(s1[i]==s2[j]) {41               f[i][j]=f[i-1][j-1]+1;42               pre[i][j]=1;43         }44           else if(f[i-1][j]>f[i][j-1]){45               f[i][j]=f[i-1][j];46               pre[i][j]=2;47         }48         else {49               f[i][j]=f[i][j-1];50               pre[i][j]=3;51         }52       }53     dfs(l1,l2);54     return 0;55 }
代码

 

1006 最长公共子序列Lcs


联系
我们