单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,十分钟搞定,LCS,2,/22,主要内容,LCS,的,定义,暴力求解,LCS,分析,LCS,的性质,导出,LCS,的,递推公式,实现算法涉及的,数据结构,降低,LCS,空间复杂度,的方法,LCS,的多解性,LCS,的应用,3,/22,LCS,的定义,最长公共子序列，即,Longest Common Subsequence,，,LCS,。,一个序列,S,任意删除若干个字符得到新序列,T,，则,T,叫做,S,的子序列；,两个序列,X,和,Y,的公共子序列中，长度最长的那个，定义为,X,和,Y,的最长公共子序列。,字符串,13,455,与,2,455,76,的最长公共子序列为,455,字符串,a,c,df,g,与,adf,c,的最长公共子序列为,adf,注意区别最长公共子串,(Longest Common Substring),最长公共字串要求连续,4,/22,LCS,的意义,求两个序列中最长的公共子序列算法，广泛的应用在图形相似处理、媒体流的相似比较、计算生物学方面。生物学家常常利用该算法进行基因序列比对，由此推测序列的结构、功能和演化过程。,LCS,可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。另一方面，对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。简而言之，百度知道、百度百科都用得上。,5,/22,暴力求解：穷举法,假定字符串,X,，,Y,的长度分别为,m,，,n,；,X,的一个子序列即下标序列,1,2,m,的严格递增子序列，因此，,X,共有,2,m,个不同子序列；同理，,Y,有,2,n,个不同子序列，从而穷举搜索法需要指数时间,O(2,m,.,2,n,),；,对,X,的每一个子序列，检查它是否也是,Y,的子序列，从而确定它是否为,X,和,Y,的公共子序列，并且在检查过程中选出最长的公共子序列；,显然，不可取。,6,/22,LCS,的记号,字符串,X,，长度为,m,，从,1,开始数；,字符串,Y,，长度为,n,，从,1,开始数；,Xi=x1,，,xi,即,X,序列的前,i,个字符,(1im)(Xi,不妨读作“字符串,X,的,i,前缀”,),Yj=y1,，,yj,即,Y,序列的前,j,个字符,(1jn)(,字符串,Y,的,j,前缀,),；,LCS(X,Y),为字符串,X,和,Y,的最长公共子序列，即为,Z=z1,，,zk,。,注：不严格的表述。事实上，,X,和,Y,的可能存在多个子串，长度相同并且最大，因此，,LCS(X,Y),严格的说，是个字符串集合。即：,Z LCS(X,Y).,7,/22,LCS,解法的探索：,x,m,=y,n,若,x,m,=y,n,(,最后一个字符相同,),，则：,X,m,与,Y,n,的最长公共子序列,Z,k,的最后一个字符必定为,x,m,(=y,n,),。,z,k,=x,m,=y,n,LCS(X,m,Y,n,)=LCS(X,m-1,Y,n-1,)+x,m,8,/22,结尾字符相等，则,LCS(X,m,Y,n,)=LCS(X,m-1,Y,n-1,)+x,m,记,LCS(X,m,Y,n,)=W+x,m,，则,W,是,X,m-1,的子序列；同理，,W,是,Y,n-1,的子序列；因此，,W,是,X,m-1,和,Y,n-1,的公共子序列。,反证：若,W,不是,X,m-1,和,Y,n-1,的,最长,公共子序列，不妨记,LCS(X,m-1,Y,n-1,)=W,，且,|W|,|W|,；那么，将,W,换成,W,，得到更长的,LCS(X,m,Y,n,)=Wx,m,，与题设矛盾。,9,/22,举例：,x,m,=y,n,1,2,3,4,5,6,7,X,B,D,C,A,B,A,Y,A,B,C,B,D,A,B,对于上面的字符串,X,和,Y,：,x,3,=y,3,=,C,，则：,LCS(BD,C,AB,C,)=LCS(BD,AB)+,C,x,5,=y,4,=,B,，则：,LCS(BDCA,B,ABC,B,)=LCS(BDCA,ABC)+,B,10,/22,LCS,解法的探索：,x,m,y,n,若,x,m,y,n,，则：要么,LCS(X,m,Y,n,)=LCS(X,m-1,Y,n,),，要么,LCS(X,m,Y,n,)=LCS(X,m,Y,n-1,),。,证明：令,Z,k,=LCS(X,m,Y,n,),；由于,x,m,y,n,则,z,k,x,m,与,z,k,y,n,至少有一个必然成立，不妨假定,z,k,x,m,（,z,k,y,n,的分析与之类似）。,因为,z,k,x,m,，则最长公共子序列,Z,k,是,X,m-1,和,Y,n,得到的，即：,Z,k,=LCS(X,m-1,Y,n,),同理，若,z,k,y,n,，则,Z,k,=LCS(X,m,Y,n-1,),即，若,x,m,y,n,，则：,LCS(X,m,Y,n,)=maxLCS(X,m-1,Y,n,),LCS(X,m,Y,n-1,),11,/22,举例：,x,m,y,n,1,2,3,4,5,6,7,X,B,D,C,A,B,A,Y,A,B,C,B,D,A,B,对于字符串,X,和,Y,：,x,2,y,2,，则：,LCS(B,D,A,B,)=max,LCS(B,D,A),LCS(B,A,B,),x,4,y,5,，则：,LCS(BDC,A,ABCB,D,)=,max,LCS(BDC,A,ABCB),LCS(BDC,ABCB,D,),12,/22,LCS,分析总结,显然，属于,动态规划,问题。,13,/22,算法中的数据结构：长度数组,使用二维数组,Cm,n,ci,j,记录序列,Xi,和,Yj,的最长公共子序列的长度。,当,i=0,或,j=0,时，空序列是,Xi,和,Yj,的最长公共子序列，故,ci,j=0,。,14,/22,算法中的数据结构：方向变量,使用二维数据,Bm,n,，其中，,bi,j,标记,ci,j,的值是由哪一个子问题的解达到的。即,ci,j,是由,ci-1,j-1+1,或者,ci-1,j,或者,ci,j-1,的哪一个得到的。取值范围为,Left,，,Top,，,LeftTop,三种情况。,15,/22,实例,X=,Y=,16,/22,计算,LCS,长度,17,/22,根据,b,提供的方向，构造最长公共子序列,18,/22,进一步思考的问题,方向数组,b,是完全可以省略的：,数组元素,ci,j,的值仅由,ci-1,j-1,，,ci-1,j,和,ci,j-1,三个值之一确定，因此，在计算中，可以临时判断,ci,j,的值是由,ci-1,j-1,，,ci-1,j,和,ci,j-1,中哪一个数值元素所确定，代价是,(1),时间。,若只计算,LCS,的长度，则空间复杂度为,min(m,n),。,在计算,ci,j,时，只用到数组,c,的第,i,行和第,i-1,行。因此，只要用,2,行的数组空间就可以计算出最长公共子序列的长度。,19,/22,最大公共子序列的多解性：求所有的,LCS,当,x,m,y,n,时：,若,LCS(X,m-1,Y,n,)=LCS(X,m,Y,n-1,),，会导致多解：有多个最长公共子序列，并且它们的长度相等。,B,的取值范围从,1,2,3,扩展到,1,2,3,4,广度优先遍历,20,/22,LCS,的应用：最长递增子序列,LIS,Longest Increasing Subsequence,给定一个长度为,N,的数组，找出一个最长的单调递增子序列。,例如：给定数组,5,，,6,，,7,，,1,，,2,，,8,，则其最长的单调递增子序列为,5,，,6,，,7,，,8,，长度为,4,。,分析：其实此,LIS,问题可以转换成最长公子序列问题，为什么呢？,21,/22,使用,LCS,解,LIS,问题,原数组为,A 5,，,6,，,7,，,1,，,2,，,8,排序后：,A1,，,2,，,5,，,6,，,7,，,8,因为，原数组,A,的子序列顺序保持不变，而且排序后,A,本身就是递增的，这样，就保证了两序列的最长公共子序列的递增特性。如此，若想求数组,A,的最长递增子序列，其实就是求数组,A,与它的排序数组,A,的最长公共子序列。,此外，本题也可以直接使用动态规划来求解,