1 最长公共子序列

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

1、1最长公共子序列日积月累-算法与2009-10-1911:08:33阅读577评论0字号：大中小订阅一个给定序列的子序列是在该序列中删去若干元素后得到的序列。最长公共子序列问题是给定两个序列X=｛x1,x2...xm}和Y={y1,y2...yn}，找出X和Y的最长公共子序列，用动态规划算法可有效的解些问题。最长公共子序列的结构：设X={x1,...,xm},Y={y1,...,yn}及它们的最长子序列Z={z1,...,zk}则1、若xm=yn，则zk=xm=yn，且Z[k-1]是X[m-1]和Y[

2、n-1]的最长公共子序列2、若xm!=yn，且zk!=xm,则Z是X[m-1]和Y的最长公共子序列3、若xm!=yn,且zk!=yn,则Z是Y[n-1]和X的最长公共子序列子问题的递归结构：当i=0,j=0时,c[i][j]=0当i,j>0;xi=yi时,c[i][j]=c[i-1][j-1]+1当i,j>0;xi!=yi时,c[i][j]=max{c[i][j-1],c[i-1][j]}由以上分析，先计算最优值，再构造最长公共子序列，C++源程序如下：#include#includ

3、e#include"iostream"usingnamespacestd;intlength=0;//记录最长公共序列长度//计算最优值voidlcs(stringx,stringy,int**b){inti,j;//获取字符串的长度intm=x.size();intn=y.size();//创建动太二维数组int**c;c=newint*[m+1];for(inti=0;i

4、[0]=0;for(i=1;i<=n;i++)c[0][i]=0;c[0][0]=0;//遍历记录最优值，并将标识存在数组b中for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i-1]==y[j-1]){//xm=yn，则zk=xm=yn，且Z[k-1]是X[m-1]和Y[n-1]的最长公共子序列c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>c[i][j-1]){//xm!=yn，且zk!=xm,则Z是X[m-1]和Y

5、的最长公共子序列c[i][j]=c[i-1][j];b[i][j]=2;}else{//xm!=yn,且zk!=yn,则Z是Y[n-1]和X的最长公共子序列c[i][j]=c[i][j-1];b[i][j]=3;}}//释放空间for(inti=0;i

6、

7、j==0)return;//从b[m][n]开始，用递归依其值在数组b

8、中搜索if(b[i][j]==1){//xi和yj的最长公共子序列是由x(i-1)和y(j-1)的最长公共子序列在尾部加上xi所得到的子序列show(i-1,j-1,x,b);length++;cout<

9、ingx;stringy;int**b;cout<<"输入第一个序列";cin>>x;cout<<"输入第二个序列";cin>>y;intm=x.size();intn=y.size();//创建二维动态数组b=newint*[m+1];for(inti=0;i

10、nti=0;i是序列X=的子序列当且仅当存在严格上升的序列,使得对j=1,2,...,k,有xij=zj。比如Z=是X=的子序列。现在给出两个序列X和Y,你的任务是找到X