且不存在比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
.性能不好。