最长公共子序列(LCS)算法及报告-Read.docVIP

最长公共子序列 (LCS)算法及报告 一、实验名称 最长公共子序列问题 二、实验目的及要求 所涉及和需要掌握的知识： 1. 最优子结构性质：当问题的最优解包含子问题的最优子结构 2. 为了解决递归的重复调用问题，采用备忘录的方法， 3. 动态规划的基本原理： 在字母表上，分别给出两个长度为n和m的字符串A和B，这里A= … 的子序列是一个形式为 … 的字符串，其中每个都在1和n之间。例如 ={x,y,z}，A=zxyxyz,B=xyyzx那么xyy同时是A和B的长度是3的子序列。然而。它不是A和B的最长的公共子序列，因为字符串xyyx也是A和B的公共的子序列。因此A和B的最长公共子序列的长度是4。 最后得到结论：如果i和j都大于0，那么 l 若 = ，L[i,j]=L[i-1,j-1]+1; l 若 != ,L[I,j]=max{L[i-1,],L[I,j-1]} 三、实验环境 操作系统:WINDOWS 2000 使用软件:VC 使用语言:C语言 四、问题描述及实验内容 假设A=”xyxxzxyzxy”和B=”zxzyyzxxyxxz”，求出A和B的最长公共子序列的长度并输出其中一个最长公共子序列。 最后求得L[n,m]=6和最长子序列为xyxxxz 五、问题分析和算法描述 LCS的算法表示： 输入：字母表上的两个字符串A和B，长度分别为n和m. 输出：A和B的最长公共子序列的长度和其中一个最长子序列。 1. for i=1 to n 2. L[i,0]=0 3. end for 4. for j=0 to m 5. L[0,j]=0 6. end for 7. for i=1 to n 8. for j=1 to m 9. if = then L[i,j]=L[i-1,j-1]+1 10. else L[I,j]=max{L[i-1,],L[I,j-1]} 11. end if 12. end for 13. end for 14. return L[n,m] LCS的图表示： 假设A=”xyxxzxyzxy”，B=”zxzyyzxxyxxz” B z x z y y z x x y x x z 0 1 2 3 4 5 6 7 8 9 10 11 12 A 0 0 0 0 0 0 0 0 0 0 0 0 0 0 x 1 0 0 1 1 1 1 1 1 1 1 1 1 1 y 2 0 0 1 1 2 2 2 2 2 2 2 2 2 x 3 0 0 1 1 2 2 2 3 3 3 3 3 3 x 4 0 0 1 1 2 2 2 3 4 4 4 4 4 z 5 0 1 1 2 2 2 3 3 4 4 4 4 5 x 6 0 1 2 2 2 2 3 4 4 4 5 5 5 y 7 0 1 2 2 3 3 3 4 4 5 5 5 5 z 8 0 1 2 3 3 3 4 4 4 5 5 5 6 x 9 0 1 2 3 3 3 4 5 5 5 6 6 6 y 10 0 1 2 3 4 4 4 5 5 6 6 6 6 表（1） 六、实验步骤及实验结果 实验的具体步骤参考附录（源程序清单）。 实验结果： 七、总结 对上面正确结果中的矩阵进行分析： 1. 若i=0或j=0 L[i,j]=0 2. 若i0,j0和 = L[i,j]=L[i-1,j-1]+1 3. 若i0,j0和 != L[I,j]=max{L[i-1,],L[I,j-1]} 根据上述3点可以得到矩阵如上 对上面正确结果中的最长公共子序列进行分析：（走得路线自定义先向上再向左） 用c[6]来存公共子序列的字符。 1. 从L[10,12]出发向上走直到遇到第一个小于L[8,12]的停止，向左走同样直到遇到第一个小于L[8,12]的停止. =z把存入c[5]=z, L[8,12]向左上角跳到 L[7，11] 2. 从L[7，11]出发向上走直到遇到第一个小于L[6，11]的停止，向左走同样直到遇到第一个小于L[6，10]的停止.把 =x存入c[4]=x,L[6,10]向左上角跳到 L[5,9] 3. 从L[5,9]出发向上走直到遇到第一个小于L[4,9]的停止，向左走同样直到遇到第一个小于L