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
