2、一个，最长公共子序列往往不止一个。e.g.X=,Y=,则Z=,Z’=,Z’’=均属于LCS(X,Y)，即X,Y有3个LCS。本文描述如何寻找所有的LCS二、问题分析①先描述寻找一个LCS的思想：记Xi=﹤x1，…，xi﹥即X序列的前i个字符(1≤i≤m)（前缀）Yj=﹤y1，…，yj﹥即Y序列的前j个字符(1≤j≤n)（前缀）假定Z=﹤z1，…，zk﹥∈LCS(X,Y)。若xm=yn（最后一个字符相同），则不难用反证法证
3、明：该字符必是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,Yn-1)。∴若xm=yn，则问题化归成求Xm-1与Yn-1的LCS，（LCS(X,Y)的长度等于LCS(X
4、m-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)的长度这两个问题不是相互独立的：∵两者都需要求LCS(Xm-1，Yn-1)的长度,因而具有重叠性。此外，两个序列的LCS中包含了两个序列的前缀的LCS，故问题具有最优子结构性质考虑用动态规划法。引进一个二维数组C，用C[i,j]记录Xi与Yj的LCS的长度。如果我们是按行、列的序号从小
5、到大地进行递推计算，（从第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]均已计算出来。此时根据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]，进行下
6、述判断：若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]是通过哪一个子问题的值求得的,以决定搜索的方向：若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]
7、，Y=，求出的各个C[i,j]与b[i,j]如下图：0123456yjBDCABA0xi0000000↑↑↑↖↖1A00001←11↖↑↖2B01←1←112←2↑↑↖↑↑3C0112←222↖↑↑↑↖4B011223←3↑↖↑↑↑↑5D0122233↑↑↑↖↑↖6A0122334↖↑↑↑↖↑7B0122344②找出所有路径的思想：仅用“↑”，“←”，“↖”是搜索不到所有的LCS的，因为C[i-1,j]≥C[i,j-1]，我们没有区分C[i-1,j]>C[i,j-1]还是C[i-1,j]＝C[i,j-1
8、]此时我们只是在单方向搜索，就像是图的深度优先搜索，走到底，找出一条路径。为了找出所有的LCS，我们将C[i-1,j]≥C[i,j-1]记做“←↑”。同时用遍历b[i,j]构造出一棵树tree，“↑”的方向记做节点的左子树，右子树为空，“←”的方向记做节点的右子
