算法LCS-所有的最长公共子序列

所有的最长公共子序列（LCS）一、问题描述子序列的概念：设X=x1,x2,┅,xm，若有1≤i1i2┅ik≤m，得Z=z1,z2,┅,zk=xi1,xi2,┅,xik，则称Z是X的子序列，记为ZX。e.g.X=A,B,C,B,D,A,B,Z=B,C,B,A,则有ZX。公共子序列的概念：设X，Y是两个序列，且有ZX和ZY，则称Z是X和Y的公共列。最长公共子序列的概念：若ZX，ZY，且不存在比Z更长的X和Y的公共子序列，则称Z是X和Y的最长公共子序列，记为ZLCS(X,Y)。但是LCS不是只有一个，最长公共子序列往往不止一个。e.g.X=A,B,C,B,D,A,B,Y=B,D,C,A,B,A,则Z=B,C,B,A,Z’=B,C,A,B,Z’’=B,D,A,B均属于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]=yxyxjijijijiCjiCjijiCji且若且若或若0,]}1,[],,1[max{0,1]1,1[000为了构造出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]C[i,j-1]，则b[i,j]中记入“←”；e.g.对于X=A,B,C,B,D,A,B，Y=B,D,C,A,B,A，求出的各个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]此时我们只是在单方向搜索，就像是图的深度优先搜索，走到底，找出一条路径。为了找出所有的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_HclassTreeNode{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#includetreenode.h#includestring#includestack.hconstintm=7,n=6;//默认x的长度为7，y的长度为6inti=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();//遍历树，找出每个节点的parentvoidtranverse(TreeNode*);//从叶子节点遍历到根，找出LCSvoidoutput();//输出所有的LCSprivate:TreeNode*root;//根StackTreeNode*stack;//用栈来记录叶子节点string*t;//字符串数组记录不同的LCS};tree::tree(intb[m+1][n+1],stringx,inti,intj){t=newstring[n];//字符串数组最长为min{x.length,y.length}for(inty=0;yn;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);}}遍历树，找出每个节点的parentvoidtree::con_parent(){inti=0;StackTreeNode*s;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();coutcurrentNode-data;TreeNode*pp=currentNode;if(currentNode-rightchild){currentNode-rightchild-parent=pp;}currentNode=currentNode-rightchild;}}//从叶子遍历到根，找出LCSvoidtree::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;countm;count++){if(temp==t[count]){flag=false;break;}}if(flag){couttemp\n;t[exsit++]=temp;}temp=;flag=true;}//找出所有的LCSvoidtree::output(){while(!stack.IsEmpty()){tranverse(stack.Top());}}#endif//test.cpp测试函数#includeiostreamusingnamespacestd;#includetree.hintmain(){intb[m+1][n+1];intc[m+1][n+1];stringx=abcdefg;stringy=fedcba;inti,j;for(i=0;i=m;i++){c[i