东莞竞价推广/seo搜索引擎优化的内容
收藏
关注给出两个字符串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
#include<stdio.h>#include<string.h>
int dp[1010][1010],d[1010][1010];
int l1,l2;
char a[1010],b[1010];
void lcs()
{
int i,j;
for(i=1;i<=l1;i++)
for(j=1;j<=l2;j++)
{
if(a[i-1]==b[j-1])
{
dp[i][j]=dp[i-1][j-1]+1;
d[i][j]=0;
}
else if(dp[i][j-1]>=dp[i-1][j])
{
dp[i][j]=dp[i][j-1];
d[i][j]=1;
}
else
{
dp[i][j]=dp[i-1][j];
d[i][j]=-1;
}
}
}
void printlcs(int x,int y)
{
if(x==0||y==0)
return ;
if(d[x][y]==0)
{
printlcs(x-1,y-1);
printf("%c",a[x-1]);
}
else if(d[x][y]==1)
printlcs(x,y-1);
else
printlcs(x-1,y);
}
int main()
{
while(~scanf("%s%s",a,b))
{
l1=strlen(a);
l2=strlen(b);
memset(dp,0,sizeof(dp));
lcs();
printlcs(l1,l2);
printf("\n");
}
return 0;
}