设序列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/