最长公共子序列

《最长公共子序列》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、最长公共子序列1．需求分析问题描述例如：序列Z=是序列X=的子序列，相应的递增下标序列为<2，3，5，7>。一般地，给定一个序列X=，则另一个序列Z=是X的子序列，是指存在一个严格递增的下标序列〈i1,i2,…,ik〉使得对于所有j=1,2,…,k使Z中第j个元素zj与X中第ij个元素相同。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。任务是：给定2个序列X、Y，求X和Y的最长公

2、共子序列Z。输入输入文件中的第1行是一个正整数，最大为数为10。依次输入序列x和y输入后确定。输出输出的显示最长公共子序列输入的x，y至少有一个的位数大于10，程序跳出，或者x,y没有最长公共子序列时则显示空。2．算法设计计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=和Y=作为输入。输出两个数组c[0..m,0..n]和b[1..m,1..n]。其中c[i,j]存储Xi与Yj的最长公共子序列的长度，b[i,j]记录指示c[i,j]的值是由哪一个

3、子问题的解达到的，这在构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录于c[m,n]中。A、在最长公共子序列问题中，用C[i][j]记录序列Xi和Yj的最长公共子序列的长度。直接利用递归式容易写出一个计算C[i][j]的递归算法，但其计算时间是随输入长度指数增长的，所以用动态规划算法自底向上计算最优值能提高算法的效率。计算最长公共子序列长度的动态规划算法LCSLength以序列X={X1，X2，、、、，Xm}和Y={Y1，Y2，、、Yn}作为输入，输出两个数组c和b。其中c[i][j]存储Xi和Yj的最

4、长公共子序列的长度，b[i][j]记录c[i][j]的值是由哪一个字问题的解得到的，这在构造最长公共子序列时要用到。问题的最优值，即X和Y的最优公共子序列的长度记录于c[m][n]中。B、由算法LCSLength计算得到的数组b可用于快速构造序列X={X1，X2，、、、，Xm}和Y={Y1，Y2，、、Yn}的最长公共子序列。首先从b[m][n]开始，沿着其中的箭头方向在数组b中搜索。当在b[i][j]中遇到‘1’时，表示Xi和Yj的最长公共子序列是由Xi-1和Yj-1的最长公共子序列在尾部加上Xi所得到的子序列。当在b[

5、i][j]中遇到‘2’时，表示Xi和Yj的最长公共子序列与Xi-1和Yj的最长公共子序列相同。当在b[i][j]中遇到‘3’时，表示Xi和Yj的最长公共子序列与Xi和Yj-1的最长公共子序列相同。c[i][j]=c[i-1][j-1]+1;b[i][j]='1';x[i-1]==y[j-1]c[i][j]=c[i-1][j];b[i][j]='2';真假c[i-1][j]>=c[i][j-1]真假c[i][j]=c[i][j-1];b[i][j]='3';经验收获和体会(必写)3．测试结果列出你的测试结果，包括输入和输出

6、。这里的测试数据应该完整和严格，最好多于需求分析中所列。4．附录　　#include#include#include#defineM10#defineN10intc[M][N];charb[M][N];voidlcslength(char*x,char*y){inti,j,m,n;m=strlen(x);n=strlen(y);for(i=0;i

7、m;i++){for(j=1;j<=n;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]='3';}}}cout<

8、

9、j==0)return;if(b[i][j]=='1'){l

10、cs(i-1,j-1,x);cout<