算法 最長公共子序列

本文格式為Word版，下載可任意編輯——算法最長公共子序列

算法最長公共子序列

最長公共子序列

1題目分析

兩個序列的最長公共子序列的長度為最優(yōu)值，利用動態(tài)規(guī)劃法

2算法構(gòu)造

引入二維數(shù)組C[i,j]記錄Xi=xl,x2,…,xi和Yj=二y1;y2,,…,yj根據(jù)子問題最優(yōu)值的遞歸關(guān)系，可自底向上建立遞推關(guān)系如下：

當i=0,j=0時,c[i][j]=0

當i,j0;xi=yi時,c[i][j]=c[i-1][j-1]+1

當i,j0;xi!=yi時,c[i][j]=max{c[i][j-1],c[i-1][j]}

3算法實現(xiàn)

#includeiostream

#includestring

usingnamespacestd;

//計算最優(yōu)值

voidLCSLength(intm,intn,char*y,char*x,int**c,int**b)

{

inti,j;

for(i=1;i=m;i++)c[i][0]=0;

for(j=0;j=n;j++)c[0][j]=0;

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]=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;}

}

}

//構(gòu)造最長公共子序列

voidLCS(inti,intj,char*x,int**b)

{

if(i==0||j==0)return;

if(b[i][j]==1){LCS(i-1,j-1,x,b);coutx[i];}

elseif(b[i][j]==2)LCS(i-1,j,x,b);

elseLCS(i,j-1,x,b);

}

//主函數(shù)

intmain()

{

算法最長公共子序列

intm,n;

char*x,*y;

int**b,**c;

voidLCSLength(intm,intn,char*y,char*x,int**c,int**b);voidLCS(inti,intj,char*x,int**b);

cout請輸入兩個序列的長度：endl;

cinmn;

x=newchar[m];

y=newchar[n];

cout請輸入兩個序列：endl;

cinxy;

b=newint*[m+1];

for(inti=0;i=m;i++)

b[i]=newint[n+1];

c=newint*[m+1];

for(intj=0;j=m;j++)

c[j]=newint[n+1];

LCSLength(m,n,x,y,c,b);

cout最長公共子序列的元素個數(shù)為c[m][n]endl;

cout該序列為:;

LCS(m,n,x,b);

coutendl;

return0;

}

4運行結(jié)果

請輸入兩個序列的長度：

5

5

請輸入兩個序列：

dfdhh