2、LCS(X,Y)。但是LCS不是只有一个,最长公共子序列往往不止一个。e.g.X=,Y=,则Z=,Z’=,____________________________________________________________________________________________________Z’’=均属于LCS(X,Y),即X,Y有3个LCS。本文描述如何寻找所有的LCS二、问题分析①先描述寻找一个LCS的思想:记Xi=﹤x1,…,xi﹥即X序列的前i个字符(1≤i≤m
3、)(前缀)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≠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,
4、Yn-1)。∴若xm=yn,则问题化归成求Xm-1与Yn-1的LCS,(LCS(X,Y)的长度等于LCS(Xm-1,Yn-1)的长度加1)若xm≠yn,则问题化归成求Xm-1与Y的LCS及X与Yn-1的LCSLCS(X,Y)的长度为:Max{LCS(Xm-1,Y)的长度,LCS(X,Yn-1____________________________________________________________________________________________________)的长度}求LCS(Xm-1,Y)的长度与LCS(X,Yn-1)的长度这两个问题不是相互独立的:∵两者都需
5、要求LCS(Xm-1,Yn-1)的长度,因而具有重叠性。此外,两个序列的LCS中包含了两个序列的前缀的LCS,故问题具有最优子结构性质考虑用动态规划法。引进一个二维数组C,用C[i,j]记录Xi与Yj的LCS的长度。如果我们是按行、列的序号从小到大地进行递推计算,(从第1行开始计算:C[1,1]、C[1,2]、。。。C[1,n],再算C[2,1]、C[2,2]、。。。C[2,n],。。。。。。。。最后计算C[m,1]、C[m,2]、。。。C[m,n],最后算出的C[m,n]即为LCS(X,Y)的长度。)那么在计算C[i,j]之前,C[i-1,j-1],C[i-1,j]与C[i,j-1]均已计
6、算出来。此时根据X[i]=Y[j]还是X[i]¹Y[j],就可以计算出C[i,j]:若X[i]=Y[j],则执行C[i,j]←C[i-1,j-1]+1;若X[i]¹Y[j],进行下述判断:若C[i-1,j]≥C[i,j-1]则C[i,j]取C[i-1,j];否则C[i,j]取C[i,j-1]。即有C[i,j]=____________________________________________________________________________________________________为了构造出LCS,使用一个m´n的二维数组b,b[i,j]记录C[i,j]是通过哪一个
7、子问题的值求得的,以决定搜索的方向:若X[i]=Y[j],则b[i,j]中记入“↖”(亦可不记);若X[i]¹Y[j]且C[i-1,j]≥C[i,j-1],则b[i,j]中记入“↑”;若X[i]¹Y[j]且C[i-1,j],Y=,求出的各个C[i,j]与b[i,j]如下图:0123456yj