最长公共子序列算法

《算法设计与分析》上机报告姓名：学号：日期：上机题目：最长公共子序列算法实验环境：CPU:2.10GHz;内存:6G;操作系统：Win764位;软件平台：VisualStudio2008;一、算法设计与分析：题目一:计算最优值给定两个序列X={x1,x2,......,xm}和Y={y1,y2,......,yn}，找出X和Y的最长公共子序列。一个给定序列的子序列是在该序列中删去若干个元素后得到的序列。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X={A，B，C，B，D，A，B}，Y={B，D，C，A，B，A}，序列{B，C，A}是X和Y的一个公共子序列，序列{B，C，B，A}也是X和Y的一个公共子序列，且为最长公共子序列。最长公共子序列问题具有最优子结构性质。设序列X={x1,x2,......,xm}和Y={y1,y2,......,yn}的最长公共子序列为Z={z1,z2,......,zk}，则（1）若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。（2）若xm!=yn且zk!=xm，则Z是Xm-1和Y的最长公共子序列。（3）若xm!=yn且zk!=yn，则Z是X和Yn-1的最长公共子序列。其中，Xm-1={x1,x2,......,xm-1}；Yn-1={y1,y2,......,yn-1}；Zk-1={z1,z2,......,zk-1}。解法：引进一个二维数组c[][]，用c[i][j]记录X[i]与Y[j]的LCS的长度，b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。我们是自底向上进行递推计算，那么在计算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]。问题的递归式写成：jijiyxandjiifyxandjiifjoriifjicjicjicjic0,0,00]),1[],1,[max(1]1,1[0],[题目二:构造最长公共子序列由算法LCS_LENGTH计算得到的数组b可用于快速构造序列X=x1,x2,…,xm和Y=y1,y2,…,yn的最长公共子序列。首先从b[m,n]开始，沿着其中的箭头所指的方向在数组b中搜索。当b[i,j]中遇到↖时，表示Xi与Yj的最长公共子序列是由Xi-1与Yj-1的最长公共子序列在尾部加上xi得到的子序列；当b[i,j]中遇到↑时，表示Xi与Yj的最长公共子序列和Xi-1与Yj的最长公共子序列相同；当b[i,j]中遇到←时，表示Xi与Yj的最长公共子序列和Xi与Yj-1的最长公共子序列相同。二、核心代码：题目一:计算最优值//b[]=0左1左上2上voidLCS(charX[],intSizeX,charY[],intSizeY,int(*c)[SIZE_Y+1],int(*b)[SIZE_Y+1]){inti,j;for(i=0;i=SizeX;i++)c[i][0]=0;for(j=0;j=SizeY;j++)c[0][j]=0;for(i=1;i=SizeX;i++)for(j=1;j=SizeY;j++){if(X[i-1]==Y[j-1]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=0;}}}题目二:构造最长公共子序列voidPrintLCS(charX[],int(*b)[SIZE_Y+1],inti,intj){if(0==i||0==j)return;if(1==b[i][j]){PrintLCS(X,b,i-1,j-1);coutX[i-1];}else{if(2==b[i][j])PrintLCS(X,b,i-1,j);elsePrintLCS(X,b,i,j-1);}}三、结果与分析：由于每次调用至少向上或向左（或向上向左同时）移动一步，故最多调用(m+n)次就会遇到i=0或j=0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为Θ(m+n)。附录（源代码）算法源代码（C++描述）#includeiostreamusingnamespacestd;#defineSIZE_X7#defineSIZE_Y6//b[]=0左1左上2上voidLCS(charX[],intSizeX,charY[],intSizeY,int(*c)[SIZE_Y+1],int(*b)[SIZE_Y+1]){inti,j;for(i=0;i=SizeX;i++)c[i][0]=0;for(j=0;j=SizeY;j++)c[0][j]=0;for(i=1;i=SizeX;i++)for(j=1;j=SizeY;j++){if(X[i-1]==Y[j-1]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=0;}}}voidPrintLCS(charX[],int(*b)[SIZE_Y+1],inti,intj){if(0==i||0==j)return;if(1==b[i][j]){PrintLCS(X,b,i-1,j-1);coutX[i-1];}else{if(2==b[i][j])PrintLCS(X,b,i-1,j);elsePrintLCS(X,b,i,j-1);}}intmain(){charY[]={'B','D','C','A','B','A','\0'};charX[]={'A','B','C','B','D','A','B','\0'};coutX=XendlY=YendlXYendl;intb[SIZE_X+1][SIZE_Y+1];intc[SIZE_X+1][SIZE_Y+1];LCS(X,SIZE_X,Y,SIZE_Y,c,b);PrintLCS(X,b,SIZE_X,SIZE_Y);coutendl;system(pause);return0;}