本文主要是介绍《算法导论》实验二：最长公共子序列（LCS）算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最长公共子序列（LCS）算法
- 一、题目描述
- 二、算法设计与分析
- 三、核心代码
- 四、实验结果
- 五、总结
- 六、附录（C++源代码）
一、题目描述
子序列定义：X=（x1，x2，····，xm），序列Z=（z1，z2，····，zk）是X的一子序列，必须满足：若X的索引中存在一个严格增的序列i1，i2，····，ik，使得对所有的j=1~k，均有xij=zj。
两个序列的公共子序列：Z是X和Y的子序列，则Z是两者的公共子序列CS。
最长公共子序列（LCS）：在X和Y的CS中，长度最大者为一个最长公共子序列LCS。
实验环境：
CPU：奔腾 T4300
内存:4G
操作系统：Windows7 ;
软件平台：VS2010
二、算法设计与分析
1、算法思想：因为LCS问题满足最优子结构和重叠子区间，所以可用动态规划的方法来设计算法。
2、LCS的最优子结构性质：
设序列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）若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；
（3）若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。
其中Xm-1=(x1, x2, …, xm-1)，Yn-1=(y1, y2, …, yn-1)，Zk-1=(z1, z2, …, zk-1)。
两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。
3、子问题的递归结构：
由最长公共子序列问题的最优子结构性质可知，要找出X=(x1, x2, …, xm)和Y=(y1, y2, …, yn)的最长公共子序列，可按以下方式递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当x
这篇关于《算法导论》实验二：最长公共子序列（LCS）算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
