最长公共子序列

《最长公共子序列》由会员分享，可在线阅读，更多相关《最长公共子序列（11页珍藏版）》请在金锄头文库上搜索。

1、最长公共子序列：最长公共子序列：应用：打字比赛（规则，中外区别） SARS病毒 文件比较等等 两个一维事物的比较定义：与子串的区别算法：穷举法，动态规划法 代码实现：用C若给定序列X=x1,x2,xm，则另一序列 Z=z1,z2,zk，是X的子序列是指存在一个严格递增 下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。 例如，序列Z=B，C，D，B是序列X=A，B，C，B ，D，A，B的子序列，相应的递增下标序列为2，3 ，5，7。而子串则要求左右两元素在母串中为相邻。 给定2个序列X和Y，当另一序列Z既是X的子序列又是 Y的子序列时，称Z是序列X和Y的公共子序列。 给定2个

2、序列X=x1,x2,xm和Y=y1,y2,yn，找 出X和Y的最长公共子序列。 最长公共子序列的定义：最长公共子序列的定义：穷举法:若要求两个序列X，Y的最长公共子序列 ， 先取得X，Y的所有子序列，并进行一一比较，共有如下不同的组合：共要进行不同的比较：2 m+n最长公共子序列的结构最长公共子序列的结构设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为 Z=z1,z2,zk ，则 (1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列 。 (2)若xmyn且zkxm，则Z是xm-1和Y的最长公共子序列。 (3)若xmyn且zkyn，则Z是X和y

3、n-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀 的最长公共子序列。因此，最长公共子序列问题具有最优子结 构性质。 子问题的递归结构子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值 的递归关系。用cij记录序列和的最长公共子序列的长度。 其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序 列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下 ，由最优子结构性质可建立递归关系如下：计算最长公共子序列的长度计算最长公共子序列的长度由于在所考虑的子问题空间中，总共有(mn)个不同 的子问题，因此，用动态规划算法

4、自底向上地计算最 优值能提高算法的效率。 void LCSLength(char x, char y,int m，int n) /* 计算最长公共子序列的长度 */int Lmn,i，j;for (i = 0; i = Lij-1)Lij= Li-1j; else Lij= Lij-1; return Lmn; 举例：填充表格i j0123456 0 1d 2b 3c 4b 5a 6d 7b bacdbd从表中找出最长公共子序列的方法：（1）从(m,n) 到 (0,0)（2）若当前格与左边一格相同，则画“ ”; 若当前格与上边一格相同，则画“ ”; 上两者都不符合，从当前格到左上格画“ ”（3

5、）从当前格向箭头方向前进一格，对此格进行（4 ）从(m,n) 到 (0,0)的不同路径中，“ ”相对应的格的 元素构成最长公共子序列。找出最长公共子序列i j0123456 00000000 10000111d 20111122b 30112222c 40112233b 50122233a 60122334d 70122344b bacdbd（bcbd,bcdb,badb）求最长公共子序列void LCS(char a,int L,int m,int n) /* 求最长公共子序列 */int i,j,k; char cm;i=m;j=n;k=m;do if(Lij=Li-1j) i-;else if(Lij=Lij-1) j-; else ck=aii; k-;i-;j-;while(i0printf(“%s”,c+k+1);时间复杂度为：m+n=O(n)算法的改进算法的改进如果只需要计算最长公共子序列的长度，则 算法的空间需求可大大减少。事实上，在计 算cij时，只用到数组c的第i行和第i-1行。 因此，用2行的数组空间就可以计算出最长公 共子序列的长度。进一步的分析还可将空间 需求减至O(min(m,n)。 思考题：如何对程序进行改正，作为思考题 。