算法LCS,所有的最長(zhǎng)公共子序列

所有的最長(zhǎng)公共子序列(LCS)一、問(wèn)題描述子序列的概念：設(shè)X=<x1,x2,…,xm>,若有iqvi2V…<ik4m,得Z=<z1,z2廣，zk>=<Xil5 Xik>，則稱Z是X的子序列，記為Z<Xoe.g.X=<A,B,C,B,D,A,B>,Z=<B,C,B,A>,則有Z<Xo公共子序列的概念：設(shè)X,Y是兩個(gè)序列，且有Z<X和Z<Y,則稱Z是X和Y的公共列。最長(zhǎng)公共子序列的概念若Z<X,Z<Y,且不存在比Z更長(zhǎng)的X和Y的公共子序列則稱Z是X和Y的最長(zhǎng)公共子序列，記為ZLCS(X,Y)但是LCS不是只有一個(gè)，最長(zhǎng)公共子序列往往不止一個(gè)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,BF均屬于LCS(X,Y)，即X,Y有3個(gè)LCS。本文描述如何尋找所有的LCS二、問(wèn)題分析①先描述尋找一個(gè)LCS的思想：記X產(chǎn)<x1 X/即X序列的前i個(gè)字符(ISiSm)(前綴)Y產(chǎn)<y1，…，yj>即Y序列的前j個(gè)字符(ISjSn)(前綴)假定Z=<z1,…,zk>￡LCS(X,Y)o若xm=yn(最后一個(gè)字符相同)，則不難用反證法證明：該字符必是X與Y的任一最長(zhǎng)公共子序列Z(設(shè)長(zhǎng)度為k)的最后一個(gè)字符，即有zk=xm=yno且顯然有ZkfLCS(Xm1,Yn1)即Z的前綴Zk1是Xm1與Yn1的最長(zhǎng)公共子序列。若xm￥yn，則亦不難用反證法證明：mn要么ZGLCS(Xm1,Y),要么Z￡LCS(X,Yn1)。由于zk*xm與zk*yn其中至少有一個(gè)必成立，因此：若zk*xm則有ZeLCS(Xm1,力，若zk*yn則有Z￡LCS(X,Yn1)o，若xm=yn，則問(wèn)題化歸成求Xm1與Yn1的LCS,(LCS(X,Y)的長(zhǎng)度等于LCS(Xm1,Yn1)的長(zhǎng)度加1)若xm*yn,則問(wèn)題化歸成求Xm1與Y的LCS及X與Yn1的

LCSLCS(X,Y)的長(zhǎng)度為：Max{LCS(Xm1,Y)的長(zhǎng)度,LCS(X,Yn1)的長(zhǎng)度}求LCS(Xm1,Y)的長(zhǎng)度與LCS(X,Yn1)的長(zhǎng)度這兩個(gè)問(wèn)題不是相互獨(dú)立的：;兩者都需要求LCS(Xm1,Yn1)的長(zhǎng)度，因而具有重疊性。此外，兩個(gè)序列的LCS中包含了兩個(gè)序列的前綴的LCS，故問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)=考慮用動(dòng)態(tài)規(guī)劃法。引進(jìn)一個(gè)二維數(shù)組C，用C[i,j]記錄X.與Y.的LCS的長(zhǎng)度。如果我們是按行、列的序號(hào)從小到大地進(jìn)行遞推計(jì)算(從第1行開(kāi)始計(jì)算：C[1,1]、C[1,2]、。。。C[1,n]，再算C[2,1]、C[2,2]、。。。C[2,n]，。。。。。。。。最后計(jì)算C[m,1]、C[m,2]、。。。C[m,n]，最后算出的C[m,n]即為L(zhǎng)CS(X,Y)的長(zhǎng)度。)那么在計(jì)算C[i,j]之前，C[i-1,j-1],C[i-1,j]與3止1]均已計(jì)算出來(lái)。此時(shí)根據(jù)X[i]=Y[j]還是X[i]wY[j]，就可以計(jì)算出C[i,j]：若X[i]=Y[j]，則執(zhí)行C[iJ]-C[i-1,j-1]+1；若X[i#Y[j]，進(jìn)行下述判斷：若C[i-1J]NC[iJ-1]則C[i,j]取C[i-1,j]；否則C[i,j]取C[i,j-1]。即有0若i=0或/=0C[i,j]=c[i-1,j-1]+1若i,j〉。且冗=yC[i,j]=max{C[i-1,j],C[i,j-1]}若i,j〉0且xwy為了構(gòu)造出LCS，使用一個(gè)mxn的二維數(shù)組b，b[i,j]記錄C[i,j]是通過(guò)哪一個(gè)子問(wèn)題的值求得的,以決定搜索的方向：若X[i]=Y[j]，則b[i,j]中記入“\”(亦可不記)；若乂口]/丫口]且C[i-1,j]之C[i,j-1]，則b[i,j]中記入“甘；若X口]工丫口]且C[i-1,j]<C[i,j-1]，則b[i,j]中記入“一”；e.g.對(duì)于X=<A,B,C,B,D,A,B>，Y=<B,D,C,A,B,A>，求出的各個(gè)C[i,j]與b[i,j]如下圖：yi

0x0

iyi

0x0

i1B0TTT\\

12345671234567ABCBDAB0X00X000X00001-11K1-1-112-2T\12—222-3T34T4」I3T3T34XXT2T23T3XT2T2T2T2T12T2T2X1T11②找出所有路徑的思想:僅用“t”，“一"，“\”是搜索不到所有的LCS的，因?yàn)镃[i-1J]>C[i,j-1],我們沒(méi)有區(qū)分C[i-1,j]>C[i,j-1]還是C[i-1,j]=C[i,j-1]此時(shí)我們只是在單方向搜索,就像是圖的深度優(yōu)先搜索,走到底,找出一條路徑。為了找出所有的LCS,我們將C[i-1,j]>C[i,j-1]記做“一T”。同時(shí)用遍歷b[i,j]構(gòu)造出一棵樹tree,"T”的方向記做節(jié)點(diǎn)的左子樹，右子樹為空，“一”的方向記做節(jié)點(diǎn)的右子樹，左子樹為空，“X”的方向開(kāi)辟新的節(jié)點(diǎn)，并對(duì)其賦值“-T”記做節(jié)點(diǎn)的左子樹和右子樹。當(dāng)樹構(gòu)造完畢時(shí)，我們從葉子節(jié)點(diǎn)開(kāi)始遍歷，一直到根為止，即找出所有的LCS。注意：此時(shí)找出的所有的LCS可能有重復(fù)的，所以用一個(gè)字符串?dāng)?shù)組來(lái)記錄不同的LCS。容易證明該字符數(shù)組最長(zhǎng)為min{x.length,y.length};三、解決方案為了方便，程序中將“T”記做1,“一”記做-1,“X”記做0“一t”記做2.//treenode.h#ifndefTREENODE_H#defineTREENODE_HclassTreeNode(friendclasstree;public://構(gòu)造函數(shù)//構(gòu)造函數(shù)data=a;leftchild=0;rightchild=0;parent=0;TreeNode*leftchild;TreeNode*rightchild;TreeNode*parent; 〃從葉子往根遍歷時(shí)找的路線chardata;}；#endif〃構(gòu)造樹//tree.h#ifndefTREE_H#defineTREE_H#include"treenode.h"#include<string>#include"stack.h"constintm=7,n=6; //默認(rèn)x的長(zhǎng)度為7,y的長(zhǎng)度為6inti=0,j=0;intexsit=0; 〃記錄字符串?dāng)?shù)組有幾個(gè)元素classtree(public:tree(intb[m+1][n+1],stringx,inti,intj);TreeNode*LCS(intb[m+1][n+1],stringx,inti,intj);//構(gòu)造樹voidinorder。；voidinorder(TreeNode*);〃中序遍歷，找出所有的葉子節(jié)點(diǎn)voidcon_parent();〃遍歷樹，找出每個(gè)節(jié)點(diǎn)的parentvoidtranverse(TreeNode*);//從葉子節(jié)點(diǎn)遍歷到根，找出LCSvoidoutput。;//輸出所有的LCSprivate:TreeNode*root;//根Stack<TreeNode*>stack;/海棧來(lái)記錄葉子節(jié)點(diǎn)string*t;//字符串?dāng)?shù)組記錄不同的LCS};tree::tree(intb[m+1][n+1],stringx,inti,intj)(t=newstring[n];//字符串?dāng)?shù)組最長(zhǎng)為min(x.length,y.length}for(inty=0;y<n;y++)(t[y]="";}root=LCS(b,x,i,j);//遞歸構(gòu)造}TreeNode*tree::LCS(intb[m+1][n+1],stringx,inti,intj)(if(i==0||j==0)(TreeNode*a=newTreeNode('$');〃默認(rèn)將節(jié)點(diǎn)值賦為‘$‘returna;}if(b[i][j]==0)(TreeNode*a=newTreeNode(x[i]);〃存在字符相等，創(chuàng)造新節(jié)點(diǎn)，并賦值a->leftchild=LCS(b,x,i-1,j-1);/莊子樹繼續(xù)構(gòu)造returna;}elseif(b[i][j]==1)(returnLCS(b,x,i-1,j);//往上面走，不創(chuàng)造新節(jié)點(diǎn)，繼續(xù)遞歸)elseif(b[i][j]==-1)(returnLCS(b,x,i,j-1);//往左面走，不創(chuàng)造新節(jié)點(diǎn)，繼續(xù)遞歸}else(左子樹和右〃遇到兩個(gè)方向的點(diǎn)，創(chuàng)造新節(jié)點(diǎn)，并默認(rèn)賦值為'遞歸構(gòu)造子樹。左子樹和右TreeNode*a=newTreeNode('#');a->leftchild=LCS(b,x,i-1,j);a->rightchild=LCS(b,x,i,j-1);returna;)}voidtree::inorder0(inorder(root);)//找出所有的葉子節(jié)點(diǎn)用棧來(lái)記錄voidtree::inorder(TreeNode*current){if(current)(inorder(current->leftchild);if(current->data=='#')stack.add(current);inorder(current->rightchild);))遍歷樹，找出每個(gè)節(jié)點(diǎn)的parentvoidtree::con_parent()(inti=0;Stack<TreeNode*>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();cout<<currentNode->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若有重復(fù)的，不存入string數(shù)組中，for(intcount=0;count<m;count++)(if(temp==t[count]){flag=false;break;))if(flag)(cout<<temp<<"\n";t[exsit++]=temp;)temp="";flag=true;〃找出所有的LCSvoidtree::output()(while(!stack.IsEmpty())(tranverse(stack.Top());))#endif//test.cpp測(cè)試函數(shù)#include<iostream>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;)//構(gòu)造出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-1]){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); 〃構(gòu)造樹t.con_par