1006 最長公共子序列Lcs 基準時間限制: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示例
abcicba
abdkscab
Output示例
abca
首先确定方程類型,二維方程 dp[i][j]=k 表示以字元串A第i個字元和字元串B第j個字元結尾的最長公共子串長度為k;
dp[i+1][j+1]=max(dp[i+1][j] ,dp[i][j+1] , dp[i][j]+1)
表示A串i+1個和B串j個取最長,A串i個和B串j+1個取最長
如果a[i]==b[j],就是取dp[i+1][j+1]=dp[i][j]+1;
代碼如下:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
using namespace std;
const int ma=1005;
int dp[ma][ma];
int main()
{
string a,b,ans;
while(cin>>a>>b)
{
int lena=a.length(),lenb=b.length(),cur=0;
ans="";
for(int i=0;i<lena;++i)
for(int j=0;j<lenb;++j)
{
if(a[i]==b[j]) dp[i+1][j+1]=dp[i][j]+1;
else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
}
int i=lena-1,j=lenb-1;
while(i>=0&&j>=0)
{
if(a[i]==b[j])
{
ans=a[i]+ans;
--i;
--j;
}
else
{
if(dp[i][j+1]>dp[i+1][j]) --i;
else --j;
}
}
cout<<ans<<endl;
}
return 0;
}