LCS最长公共子序列

相关的介绍

描述

在两个字符串序列中,寻找到最长的公共子序列。

概念与性质

子串:在目标串中连续的多个元素的集合体(在模板串内一定能找到一样的串)
子序列:在目标串中多个元素在不改变相对前后关系下的集合。

总结

算法使用了二维数组进行搜索和查找,这样就限定了其所能查找的范围是两个比较小的串。
使用的思想是递推的思想将从上向下、从左到右填充表格,每个单元格包含一个数字,代表该行和该列之前的两个字符串的 LCS 的长度。也就是说,每个单元格包含原始问题的一个字问题的解。
如下图的类推。
fuck 1
fuck 2
fuck 3
每一个点的值跟他的左边的,上边的,左上方的只有关系。
可以证得:
在空单元格中填充下面 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/5806085

1
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];
}