十分钟搞定LCS.

十分钟搞定LCS2/22julyedu.com主要内容LCS的定义暴力求解LCS分析LCS的性质导出LCS的递推公式实现算法涉及的数据结构降低LCS空间复杂度的方法LCS的多解性LCS的应用3/22julyedu.comLCS的定义最长公共子序列，即LongestCommonSubsequence，LCS。一个序列S任意删除若干个字符得到新序列T，则T叫做S的子序列；两个序列X和Y的公共子序列中，长度最长的那个，定义为X和Y的最长公共子序列。字符串13455与245576的最长公共子序列为455字符串acdfg与adfc的最长公共子序列为adf注意区别最长公共子串(LongestCommonSubstring)最长公共字串要求连续4/22julyedu.comLCS的意义求两个序列中最长的公共子序列算法，广泛的应用在图形相似处理、媒体流的相似比较、计算生物学方面。生物学家常常利用该算法进行基因序列比对，由此推测序列的结构、功能和演化过程。LCS可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。另一方面，对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。简而言之，百度知道、百度百科都用得上。5/22julyedu.com暴力求解：穷举法假定字符串X，Y的长度分别为m，n；X的一个子序列即下标序列{1,2,…,m}的严格递增子序列，因此，X共有2m个不同子序列；同理，Y有2n个不同子序列，从而穷举搜索法需要指数时间O(2m.2n)；对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列；显然，不可取。6/22julyedu.comLCS的记号字符串X，长度为m，从1开始数；字符串Y，长度为n，从1开始数；Xi=﹤x1，⋯，xi﹥即X序列的前i个字符(1≤i≤m)(Xi不妨读作“字符串X的i前缀”)Yj=﹤y1，⋯，yj﹥即Y序列的前j个字符(1≤j≤n)(字符串Y的j前缀)；LCS(X,Y)为字符串X和Y的最长公共子序列，即为Z=﹤z1，⋯，zk﹥。注：不严格的表述。事实上，X和Y的可能存在多个子串，长度相同并且最大，因此，LCS(X,Y)严格的说，是个字符串集合。即：Z∈LCS(X,Y).7/22julyedu.comLCS解法的探索：xm=yn若xm=yn(最后一个字符相同)，则：Xm与Yn的最长公共子序列Zk的最后一个字符必定为xm(=yn)。zk=xm=ynLCS(Xm,Yn)=LCS(Xm-1,Yn-1)+xm8/22julyedu.com结尾字符相等，则LCS(Xm,Yn)=LCS(Xm-1,Yn-1)+xm记LCS(Xm,Yn)=W+xm，则W是Xm-1的子序列；同理，W是Yn-1的子序列；因此，W是Xm-1和Yn-1的公共子序列。反证：若W不是Xm-1和Yn-1的最长公共子序列，不妨记LCS(Xm-1,Yn-1)=W’，且|W’|＞|W|；那么，将W换成W’，得到更长的LCS(Xm,Yn)=W’xm，与题设矛盾。9/22julyedu.com举例：xm=yn1234567XBDCABAYABCBDAB对于上面的字符串X和Y：x3=y3=‘C’，则：LCS(BDC,ABC)=LCS(BD,AB)+‘C’x5=y4=‘B’，则：LCS(BDCAB,ABCB)=LCS(BDCA,ABC)+‘B’10/22julyedu.comLCS解法的探索：xm≠yn若xm≠yn，则：要么LCS(Xm,Yn)=LCS(Xm-1,Yn)，要么LCS(Xm,Yn)=LCS(Xm,Yn-1)。证明：令Zk=LCS(Xm,Yn)；由于xm≠yn则zk≠xm与zk≠yn至少有一个必然成立，不妨假定zk≠xm（zk≠yn的分析与之类似）。因为zk≠xm，则最长公共子序列Zk是Xm-1和Yn得到的，即：Zk=LCS(Xm-1,Yn)同理，若zk≠yn，则Zk=LCS(Xm,Yn-1)即，若xm≠yn，则：LCS(Xm,Yn)=max{LCS(Xm-1,Yn),LCS(Xm,Yn-1)}11/22julyedu.com举例：xm≠yn1234567XBDCABAYABCBDAB对于字符串X和Y：x2≠y2，则：LCS(BD,AB)=max{LCS(BD,A),LCS(B,AB)}x4≠y5，则：LCS(BDCA,ABCBD)=max{LCS(BDCA,ABCB),LCS(BDC,ABCBD)}12/22julyedu.comLCS分析总结显然，属于动态规划问题。nmnmnmnmmnmnmyxYXLCSYXLCSyxxYXLCSYXLCS当当1111,,,max,,13/22julyedu.com算法中的数据结构：长度数组使用二维数组C[m,n]c[i,j]记录序列Xi和Yj的最长公共子序列的长度。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。jijiyxjijicjicyxjijicjijic且当且当或者当,0,01,,,1max,0,011,1000,14/22julyedu.com算法中的数据结构：方向变量使用二维数据B[m,n]，其中，b[i,j]标记c[i,j]的值是由哪一个子问题的解达到的。即c[i,j]是由c[i-1,j-1]+1或者c[i-1,j]或者c[i,j-1]的哪一个得到的。取值范围为Left，Top，LeftTop三种情况。15/22julyedu.com实例X=A，B，C，B，D，A，BY=B，D，C，A，B，A16/22julyedu.com计算LCS长度17/22julyedu.com根据b提供的方向，构造最长公共子序列18/22julyedu.com进一步思考的问题方向数组b是完全可以省略的：数组元素c[i,j]的值仅由c[i-1,j-1]，c[i-1,j]和c[i,j-1]三个值之一确定，因此，在计算中，可以临时判断c[i,j]的值是由c[i-1,j-1]，c[i-1,j]和c[i,j-1]中哪一个数值元素所确定，代价是Ο(1)时间。若只计算LCS的长度，则空间复杂度为min(m,n)。在计算c[i,j]时，只用到数组c的第i行和第i-1行。因此，只要用2行的数组空间就可以计算出最长公共子序列的长度。19/22julyedu.com最大公共子序列的多解性：求所有的LCS当xm≠yn时：若LCS(Xm-1,Yn)=LCS(Xm,Yn-1)，会导致多解：有多个最长公共子序列，并且它们的长度相等。B的取值范围从1,2,3扩展到1,2,3,4广度优先遍历nmnmnmnmmnmnmyxYXLCSYXLCSyxxYXLCSYXLCS当当1111,,,max,,20/22julyedu.comLCS的应用：最长递增子序列LISLongestIncreasingSubsequence给定一个长度为N的数组，找出一个最长的单调递增子序列。例如：给定数组{5，6，7，1，2，8}，则其最长的单调递增子序列为{5，6，7，8}，长度为4。分析：其实此LIS问题可以转换成最长公子序列问题，为什么呢？21/22julyedu.com使用LCS解LIS问题原数组为A{5，6，7，1，2，8}排序后：A’{1，2，5，6，7，8}因为，原数组A的子序列顺序保持不变，而且排序后A’本身就是递增的，这样，就保证了两序列的最长公共子序列的递增特性。如此，若想求数组A的最长递增子序列，其实就是求数组A与它的排序数组A’的最长公共子序列。此外，本题也可以直接使用动态规划来求解