且不存在比Z更长的X和Y的公共子序列，
则称Z是X和Y的最长公共子序列，记为ZLCS（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）（前缀）
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,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）的长度这两个问题不是相互独立的：
∵两者都需要求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]均已计算出来。
此时
根据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，使用一个mn的二维数组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]e.g.对于X=，Y=，
求出的各个C[i,j]与b[i,j]如下图：
0123456
yjBDCABA
0xi0000000
↑↑↑↖↖
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]
此时我们只是在单方向搜索，就像是图的深度优先搜索，走到底，找出一条路径。
为了找出所有的LCS，我们将C[i-1,j]≥C[i,j-1]记做“←↑”。
同时用遍历b[i,j]构造出一棵树tree，“↑”的方向记做节点的左子树，右子树为空，“←”的方向记做节点的右子树，左子树为空，“↖”的方向开辟新的节点，并对其赋值，“←↑”记做节点的左子树和右子树。
当树构造完毕时，我们从叶子节点开始遍历，一直到根为止，即找出所有的LCS。
注意：
此时找出的所有的LCS可能有重复的，所以用一个字符串数组来记录不同的LCS。
容易证明该字符数组最长为min{x.length,y.length};
三、解决方案
为了方便，程序中将“↑”记做1，“←”记做-1，“↖”记做0，“←↑”记做2.
//treenode.h
#ifndefTREENODE_H
#defineTREENODE_H
classTreeNode
{
friendclasstree;
public:
TreeNode（chara=0）//构造函数
{
data=a;
leftchild=0;
rightchild=0;
parent=0;
}
TreeNode*leftchild;
TreeNode*rightchild;
TreeNode*parent;//从叶子往根遍历时找的路线
chardata;
};
#endif
//构造树
//tree.h
#ifndefTREE_H
#defineTREE_H
#include"treenode.h"
#include
#include"stack.h"
constintm=7,n=6;//默认x的长度为7，y的长度为6
inti=0,j=0;
intexsit=0;//记录字符串数组有几个元素
classtree
{
public:
tree（intb[m+1][n+1],stringx,inti,intj）;
TreeNode*LCS（intb[m+1][n+1],stringx,inti,intj）;
//构造树
voidinorder（）;
voidinorder（TreeNode*）;
//中序遍历，找出所有的叶子节点
voidcon_parent（）;//遍历树，找出每个节点的parent
voidtranverse（TreeNode*）;//从叶子节点遍历到根，找出LCS
voidoutput（）;//输出所有的LCS
private:
TreeNode*root;//根
Stackstack;//用栈来记录叶子节点
string*t;//字符串数组记录不同的LCS
};
tree:
:
tree（intb[m+1][n+1],stringx,inti,intj）
{
t=newstring[n];//字符串数组最长为min{x.length,y.length}
for（inty=0;y{
t[y]="";
}
root=LCS（b,x,i,j）;//递归构造
}
TreeNode*tree:
:
LCS（intb[m+1][n+1],stringx,inti,intj）
{
if（i==0||j==0）
{
TreeNode*a=newTreeNode（'$'）;//默认将节点值赋为’$’
returna;
}
if（b[i][j]==0）
{
TreeNode*a=newTreeNode（x[i]）;
//存在字符相等，创造新节点，并赋值
a->leftchild=LCS（b,x,i-1,j-1）;//左子树继续构造
returna;
}
elseif（b[i][j]==1）
{
returnLCS（b,x,i-1,j）;//往上面走，不创造新节点，继续递归
}
elseif（b[i][j]==-1）
{
returnLCS（b,x,i,j-1）;//往左面走，不创造新节点，继续递归
}
else
{
//遇到两个方向的点，创造新节点，并默认赋值为’#’,递归构造左子树和右子树。
TreeNode*a=newTreeNode（'#'）;
a->leftchild=LCS（b,x,i-1,j）;
a->rightchild=LCS（b,x,i,j-1）;
returna;
}
}
voidtree:
:
inorder（）
{
inorder（root）;
}
//找出所有的叶子节点用栈来记录
voidtree:
:
inorder（TreeNode*current）
{
if（current）
{
inorder（current->leftchild）;
if（current->data=='#'）
stack.add（current）;
inorder（current->rightchild）;
}
}
遍历树，找出每个节点的parent
voidtree:
:
con_parent（）
{
inti=0;
Stacks;
TreeNode*currentNode=root;
while
（1）
{
while（currentNode）
{
s.add（currentNode）;
TreeNode*pp=currentNode;
if（currentNode->leftchild）
{
currentNode->leftchild->parent=pp;
}
currentNode=currentNode->leftchild;
}
if（s.IsEmpty（））return;
currentNode=s.Top（）;
cout<data<<"";
TreeNode*pp=currentNode;
if（currentNode->rightchild）
{
currentNode->rightchild->parent=pp;
}
currentNode=currentNode->rightchild;
}
}
//从叶子遍历到根，找出LCS
voidtree:
:
tranverse（TreeNode*leaf）
{
TreeNode*currentNode=leaf;
stringtemp="";
boolflag=true;
while（currentNode->parent）
{
if（currentNode->data!
='#'&¤tNode->data!
='$'）
{
temp=temp+currentNode->data+"";
}
currentNode=currentNode->parent;
}
if（root->data!
=’#’）//若根有非真值添加到其中去
{
temp+=root->data;
}
//看LCS若有重复的，不存入string数组中，
for（intcount=0;count{
if（temp==t[count]）
{
flag=false;
break;
}
}
if（flag）
{
cout<t[exsit++]=temp;
}
temp="";
flag=true;
}
//找出所有的LCS
voidtree:
:
output（）
{
while（!
stack.IsEmpty（））
{
tranverse（stack.Top（））;
}
}
#endif
//test.cpp测试函数
#include
usingnamespacestd;
#include"tree.h"
intmain（）
{
intb[m+1][n+1];
intc[m+1][n+1];
stringx="abcdefg";
stringy="fedcba";
inti,j;
for（i=0;i<=m;i++）
{
c[i][0]=0;
b[i][0]=0;
}
for（j=1;j<=n;j++）
{
c[0][j]=0;
b[0][j]=0;
}
//构造出c[i][j],b[i][j]
for（i=1;i<=m;i++）
{
for（j=1;j<=n;j++）
{
if（x[i]==y[j]）
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=0;
}
elseif（c[i-1][j]>c[i][j-1]）
{
c[i][j]=c[i-1][j];
b[i][j]=1;
}
elseif（c[i-1][j]{
c[i][j]=c[i][j-1];
b[i][j]=-1;
}
else
{
c[i][j]=c[i-1][j];
b[i][j]=2;
}
}
}
treet（b,x,7,6）;//构造树
t.con_parent（）;//找出每个节点的parent
t.inorder（）;//找出所有的叶子节点
t.output（）;//输出所有的LCS
return0;
}
四、输出结果
X=,Y=
X=y=
x=,y=
五、性能分析
显然，构造二维数组b，c时间为θ
；构造树时间，T（n）=2T（n-1）时间为O
;找出parent节点的时间为O（
logn），从叶子遍历到根时间为O（
logn）;该算法复杂度为O
.性能不好。
升级会员 