設(shè)序列X={x1,x2,x3......xm}和Y={y1,y2,y3,....yn}，要求最長(zhǎng)公共子序列，可以按照下面方式遞歸計(jì)算，：當(dāng)xm=yn時(shí)，找出Xm-1和Yn-1的最長(zhǎng)公共子序列，然后在其尾部加上xm即可得到X和Y的最長(zhǎng)公共子序列，當(dāng)xm不等于yn的時(shí)候，必須解決兩個(gè)子問題即找出Xm-1和Y的最長(zhǎng)公共子序列和Yn-1和X的最長(zhǎng)工公共子序列，然后這兩個(gè)里面較長(zhǎng)者為X和Y的最長(zhǎng)公共子序列！
首先建立子問題的最優(yōu)值遞歸關(guān)系。用C[i][j]表示Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。其中，Xi={x1,x2,x3......xi},Yj={y1,y2,y3,....yn}，當(dāng)i=0或者j=0時(shí)空序列是Xi和Yj的最長(zhǎng)公共子序列，故因此，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述
最長(zhǎng)公共子串（Longest common substring, 簡(jiǎn)稱LCS）問題指的是求出給定的一組
字符串的長(zhǎng)度最大的共有的子字符串。
舉例說明，以下三個(gè)字符串的LCS就是 cde：
abcde
cdef
ccde
現(xiàn)在的情況是給你2個(gè)字符串，請(qǐng)找到他們的LCS
請(qǐng)注意：字符可以不相鄰；
輸入
輸入第一行包含一個(gè)整數(shù)T，表示有T組數(shù)據(jù)；
對(duì)于每組數(shù)據(jù)包含2行，每行包含一個(gè)非空字符串，長(zhǎng)度不超過1000個(gè)字符
輸出
對(duì)于每組數(shù)據(jù)輸出他們的LCS的長(zhǎng)度，保證每組數(shù)據(jù)存在LCS；
樣例輸入
2
abcde
cdef
aaaaaaa
aaabaaa
樣例輸出
3
6
分析：
設(shè)序列X={x1,x2,x3......xm}和Y={y1,y2,y3,....yn}，要求最長(zhǎng)公共子序列，可以按照下面方式遞歸計(jì)算，：當(dāng)xm=yn時(shí)，找出Xm-1和Yn-1的最長(zhǎng)公共子序列，然后在其尾部加上xm即可得到X和Y的最長(zhǎng)公共子序列，當(dāng)xm不等于yn的時(shí)候，必須解決兩個(gè)子問題即找出Xm-1和Y的最長(zhǎng)公共子序列和Yn-1和X的最長(zhǎng)工公共子序列，然后這兩個(gè)里面較長(zhǎng)者為X和Y的最長(zhǎng)公共子序列！
首先建立子問題的最優(yōu)值遞歸關(guān)系。用C[i][j]表示Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。其中，Xi={x1,x2,x3......xi},Yj={y1,y2,y3,....yn}，當(dāng)i=0或者j=0時(shí)空序列是Xi和Yj的最長(zhǎng)公共子序列，故因此，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
實(shí)現(xiàn)代碼如下：
#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/