设序列X={x1,x2,x3......xm}和Y={y1,y2,y3,....yn},要求最长公共子序列,可以按照下面方式递归计算,:当xm=yn时,找出Xm-1和Yn-1的最长公共子序列,然后在其尾部加上xm即可得到X和Y的最长公共子序列,当xm不等于yn的时候,必须解决两个子问题即找出Xm-1和Y的最长公共子序列和Yn-1和X的最长工公共子序列,然后这两个里面较长者为X和Y的最长公共子序列!
首先建立子问题的最优值递归关系。用C[i][j]表示Xi和Yj的最长公共子序列的长度。其中,Xi={x1,x2,x3......xi},Yj={y1,y2,y3,....yn},当i=0或者j=0时空序列是Xi和Yj的最长公共子序列,故因此,C[i][j]=0,即有
代码如下:
C[i][j]=0,(i=0,j=0)
C[i][j]=c[i-1][j-1]+1,xi=yj
C[i][j]=max(C[i][j-1],C[i-1][j]),i,j>0,xi不等于yj述
最长公共子串(Longest common substring, 简称LCS)问题指的是求出给定的一组
字符串的长度最大的共有的子字符串。
举例说明,以下三个字符串的LCS就是 cde:
abcde
cdef
ccde
现在的情况是给你2个字符串,请找到他们的LCS
请注意:字符可以不相邻;
输入
输入第一行包含一个整数T,表示有T组数据;
对于每组数据包含2行,每行包含一个非空字符串,长度不超过1000个字符
输出
对于每组数据输出他们的LCS的长度,保证每组数据存在LCS;
样例输入
2
abcde
cdef
aaaaaaa
aaabaaa
样例输出
3
6
分析:
设序列X={x1,x2,x3......xm}和Y={y1,y2,y3,....yn},要求最长公共子序列,可以按照下面方式递归计算,:当xm=yn时,找出Xm-1和Yn-1的最长公共子序列,然后在其尾部加上xm即可得到X和Y的最长公共子序列,当xm不等于yn的时候,必须解决两个子问题即找出Xm-1和Y的最长公共子序列和Yn-1和X的最长工公共子序列,然后这两个里面较长者为X和Y的最长公共子序列!
首先建立子问题的最优值递归关系。用C[i][j]表示Xi和Yj的最长公共子序列的长度。其中,Xi={x1,x2,x3......xi},Yj={y1,y2,y3,....yn},当i=0或者j=0时空序列是Xi和Yj的最长公共子序列,故因此,C[i][j]=0,即有
C[i][j]=0,(i=0,j=0)
C[i][j]=c[i-1][j-1]+1,xi=yj
C[i][j]=max(C[i][j-1],C[i-1][j]),i,j>0,xi不等于yj
实现代码如下:
#include<stdio.h>
#include<string.h>
int c[1002][1002]={0};
int main()
{
int N,m,n,i,j;
char x[1002],y[1002];
scanf("%d",&N);
while(N--)
{
scanf("%s",x);
scanf("%s",y);
m=strlen(x);
n=strlen(y);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(x[i-1]==y[j-1])
{
c[i][j]=c[i-1][j-1]+1;
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
}
else
{
c[i][j]=c[i][j-1];
}
}
printf("%d\n",c[m][n]);
}
return 0;
}
参考自:
http://yangchuanhuahpu.blog.163.com/blog/static/18631884020125272205862/