相关的介绍
描述
概念与性质
子串：在目标串中连续的多个元素的集合体（在模板串内一定能找到一样的串）
子序列：在目标串中多个元素在不改变相对前后关系下的集合。
总结
算法使用了二维数组进行搜索和查找，这样就限定了其所能查找的范围是两个比较小的串。
使用的思想是递推的思想将从上向下、从左到右填充表格，每个单元格包含一个数字，代表该行和该列之前的两个字符串的 LCS 的长度。也就是说，每个单元格包含原始问题的一个字问题的解。
如下图的类推。
每一个点的值跟他的左边的，上边的，左上方的只有关系。
可以证得：
在空单元格中填充下面 3 个数字中的最大值：
V1（左）
V2（上）
如果 C1 等于 C2 则为 V3 + 1，如果 C1 不等于 C2，则为 V3 ，其中 C1 是当前单元格上面的字符，C2 是当前单元格左侧的字符
http://blog.csdn.net/leohxj/article/details/6003430
代码
源于http://blog.csdn.net/xiaotaoqibao/article/details/58060851
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#define N 10001 /*字符串长度*/
int longest[N][N];
int LCS(char *s1,char *s2)
{
int i,j,len1,len2;
len1 = strlen(s1);
len2 = strlen(s2);
longest[0][0] = 0;
for(i=1; i<=len1; i++) longest[i][0] = 0;
for(i=1; i<=len1; i++) longest[0][i] = 0;
for (i=1; i<=len1; i++)
{
for (j=1; j<=len2; j++)
{
if(s1[i-1] == s2[j-1])
longest[i][j] = longest[i-1][j-1]+1;
else if(longest[i-1][j]>longest[i][j-1])
longest[i][j] = longest[i-1][j];
else
longest[i][j] = longest[i][j-1];
}
}
return longest[len1][len2];
}