【基础算法】求最长公共子序列
【基础算法】求最长公共子序列
时间限制: 1 Sec
内存限制: 64 MB
题目描述
一个给定序列的子序列是在该序列中删去若干元素（也可以不删去）后得到的序列。例如Z="BCDB" 就是X＝"ABCBDAB"的一个子序列，而Z="CBBD"则不是X的子序列。 给定三个序列 X，Y和Z，如果Z既是X的一个子序列又是Y的一个子串，则称Z是X和Y的公共子序列。
例如X＝"ABCBDAB"，Y＝BDCABA",则序列"BCA"即为X和Y的一个公共子序列，但不是X和Y的最长公共子序列(LCS)，因为还有比它更长的公共子序列"BCBA"。事实上"BCBA"是X和Y的一个LCS ，"BDAB"也是一个LCS。
现输入两个序列X和Y，要求出X和Y的最长公共子序列。
输入
第1行：两个用字符串表示的序列X和Y。1<=X.size(),Y.size()<=1000，两个序列之间用1个空格分隔。序列均由大写字母组成。
输出
第1行：一个整数L，表示两个序列的最长公共子序列的长度。
第2行：一个字符串S，表示两个序列的最长公共子序列。如果存在多个长度等于L的子序列，输出在X序列中位置最靠前的一个。
样例输入
(如果复制到控制台无换行，可以先粘贴到文本编辑器，再复制)
ABCBDAB BDCABA
样例输出
4
BCBA
ans[i][j]表示a[0...i-1]与b[0...j-1]的最长公共序列
若a[i-1]==b[j-1]那么便匹配上了一个字符ans[i][j]=ans[i-1][j-1]+1;
若a[i-1]!=b[j-1]那么尝试匹配a[i-2]与b[j-1]或匹配a[i-1]与b[j-2]
ans[i][j]=max{ans[i-1][j],ans[i][j-1]};
代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#define INF 0x3f3f3f3f
#define LL long long int
LL getint(){
LL ans=0,f=1;char c;
while((c=getchar())<'0'||c>'9')if(c=='-')f=-f;
while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
return ans*f;
}
using namespace std;
char a[1200],b[1200];
int ans[1200][1200],len1,len2;
void print(int m,int n,int an)
{
if(!an)return;
int k=ans[m][n],i=m,j=n-1;
while(ans[i][n]==k&&i>0)i--;
while(a[i]!=b[j]&&j>0)j--;
print(i,j,an-1);
printf("%c",a[i]);
}
int main(){
int i,j;
scanf("%s%s",a,b);
len1=strlen(a);len2=strlen(b);
for(i=1;i<=len1;i++){
for(j=1;j<=len2;j++){
if(a[i-1]==b[j-1])ans[i][j]=ans[i-1][j-1]+1;
else ans[i][j]=max(ans[i-1][j],ans[i][j-1]);
}
}
printf("%d\n",ans[len1][len2]);
print(len1,len2,ans[len1][len2]);
}
版权声明：本文为qq_33927580原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。