文档介绍：程序员编程艺术第十一章:最长公共子序列(LCS)问题0、序言   程序员编程艺术系列重新开始创作了(前十章,请参考程序员编程艺术第一~十章集锦和总结)。回顾之前前十章,有些代码是值得商榷,因当初代码只顾叙述算法原理或思想,所以,很多和代码规范相关问题全部未能做到完美。以后,会着力修缮之。   搜遍网上,讲解这个LCS问题文章不计其数,但大多给读者一个并不友好感觉,稍感晦涩,且代码也不够清楚。本文力图避免此些情况。力保通俗,叙述详尽。同时,经典算法研究系列第三章(三、dynamicprogramming)也叙述了此LCS问题。有任何问题,欢迎不吝赐教。第一节、问题描述   什么是最长公共子序列呢?好比一个数列 S,假如分别是两个或多个已知数列子序列,且是全部符合此条件序列中最长,则S 称为已知序列最长公共子序列。   举个例子,如:有两条随机序列,如13455,and245576,则它们最长公共子序列便是:455。   注意最长公共子串(monSubstring)和最长公共子序列(monSubsequence,LCS)区分:子串(Substring)是串一个连续部分,子序列(Subsequence)则是从不改变序列次序,而从序列中去掉任意元素而取得新序列;更简略地说,前者(子串)字符位置必需连续,后者(子序列LCS)则无须。比如字符串acdfg同akdfc最长公共子串为df,而她们最长公共子序列是adf。LCS能够使用动态计划法处理。下文具体描述。第二节、LCS问题处理思绪穷举法      解最长公共子序列问题时最轻易想到算法是穷举搜索法,即对X每一个子序列,检验它是否也是Y子序列,从而确定它是否为X和Y公共子序列,而且在检验过程中选出最长公共子序列。X和Y全部子序列全部检验过后即可求出X和Y最长公共子序列。X一个子序列对应于下标序列{1,2,…,m}一个子序列,所以,X共有2m个不一样子序列(Y亦如此,如为2^n),从而穷举搜索法需要指数时间(2^m*2^n)。动态计划算法   实际上,最长公共子序列问题也有最优子结构性质。记:Xi=﹤x1,⋯,xi﹥即X序列前i个字符(1≤i≤m)(前缀)Yj=﹤y1,⋯,yj﹥即Y序列前j个字符(1≤j≤n)(前缀)假定Z=﹤z1,⋯,zk﹥∈LCS(X,Y)。若xm=yn(最终一个字符相同),则不难用反证法证实:该字符必是X和Y任一最长公共子序列Z(设长度为k)最终一个字符,即有zk=xm=yn且显然有Zk-1∈LCS(Xm-1,Yn-1)即Z前缀Zk-1是Xm-1和Yn-1最长公共子序列。此时,问题化归成求Xm-1和Yn-1LCS(LCS(X,Y)长度等于LCS(Xm-1,Yn-1)长度加1)。若xm≠yn,则亦不难用反证法证实:要么Z∈LCS(Xm-1,Y),要么Z∈LCS(X,Yn-1)。因为zk≠xm和zk≠yn其中最少有一个必成立,若zk≠xm则有Z∈LCS(Xm-1,Y),类似,若zk≠yn则有Z∈LCS(X,Yn-1)。此时,问题化归成求Xm-1和YLCS及X和Yn-1LCS。LCS(X,Y)长度为:max{LCS(Xm-1,Y)长度,LCS(X,Yn-1)长度}。   因为上述当xm≠yn情况中,求LCS(Xm-1,Y)长度和LCS(X,Yn-1)长度,这两个问题不是相互独立:二者全部需要求LCS(Xm-1,Yn-1)长度。另外两个序列LCS中包含了两个序列前缀LCS,故问题含有最优子结构性质考虑用动态计划法。   也就是说,处理这个LCS问题,你要求三个方面东西:1、LCS(Xm-1,Yn-1)+1;2、LCS(Xm-1,Y),LCS(X,Yn-1);3、max{LCS(Xm-1,Y),LCS(X,Yn-1)}。   行文至此,其实对这个LCS动态计划解法已叙述殆尽,不过,为了成书某种必需性,下面,我试着再多加具体叙述这个问题。第三节、、最长公共子序列结构   最长公共子序列结构有以下表示:   设序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>一个最长公共子序列Z=<z1,z2,…,zk>,则:若xm=yn,则zk=xm=yn且Zk-1是Xm-1和Yn-1最长公共子序列;若xm≠yn且zk≠xm,则Z是Xm-1和Y最长公共子序列;若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