湖南涉外经济学院计算机科学与技术专业
《算法设计与分析》课程
最长公共子序列问题
实验报告
班级：学号：姓名：教师：成绩：
2012年5月
f【实验目的】1掌握动态规划和LCS的相关算法2利用动态规划的思想实现最长公共子序列3分析实验结果，总结算法的时间和空间复杂度。【系统环境】Wi
dows7平台【实验工具】VC60中文企业版【问题描述】描述：在给定的两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是X和Y的公共子序列；给定两个序列Xx1x2……xm和Yy1y2……y
找出X和Y的最长公共子序列。要求：①、在算法LCSLe
gth和LCS中，可进一步将数组的B省去。事实上，数组元素Cij的值仅有Ci1j1Ci1j和Cij1这三个数组元素的值所确定。②、在只需要计算最长公共子序列的长度时只用到C数组的第i行和第i1行。
例：若XABCBDABYBDCABA则序列BCA是X和Y的一个公共子序列，但它不是X和Y的一个最长公共子序列。序列BCBA也是X和Y的一个公共子序列，它的长度为4，而且它是X和Y的最长公共子序列，因为X和Y没有长度大于4的公共子序列。【实验原理】一、最长公共子序列具有最优子结构：
设序列Xx1x2…xmYy1y2…y
Zz1z2…zk则1若xmy
则Zk1是Xm1和Y
1的最长公共子序列；X…CY…C如：则Z…C；2若xm≠y
且zk≠xm，Z是Xm1和Y的最长公共子序列；X…CY…则如：Bzk≠C则在计算最长公共子序列时，可不考虑X的最后一个元素C；3若xm≠y
且zk≠y
，Z是X和Y
1的最长公共子序列如：…CY…B则Xzk≠B则在计算最长公共子序列时，可不考虑Y的最后一个元素B
f二、最长公共子序列具有重叠子性质：由最长公共子序列问题的最优子结构性质可知，要找出Xx1x2…xm和Yy1y2…y
的最长公共子序列，可按以下方式递归地进行：当xmy
是，找出Xm1和Y
1的最长公共子序列，然后再其尾部加上xm（y
）即可得X和Y的最长公共子序列。当Xm≠y
时，必须解两个子问题，即找出Xm1和Y的一个最长公共子序列及X和Y
1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的最长公共子序列。由此递归结构容易看到，最长公共子序列问题具有子问题的重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算X和Y
1及Xm1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm1r