算法 最长公共子序列

算法 最长公共子序列

最长公共子序列

1题目分析

两个序列的最长公共子序列的长度为最优值，利用动态规划法

2算法构造

引入二维数组C[i,j]记录Xi = < xl,x2 , … , xi>和Yj =二< y1 ;y2 , ,…, yj > 根据子问题最优值的递归关系，可自底向上建立递推关系如下：

当 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] }

3算法实现

#include <iostream>

#include <string>

using namespace std;

//计算最优值

void LCSLength(int m,int n,char *y,char *x,int **c,int **b)

{

int i,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;}

else if(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;}

}

}

//构造最长公共子序列

void LCS(int i,int j,char *x,int**b)

{

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

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

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

else LCS(i,j-1,x,b);

}

//主函数

int main()

{

算法 最长公共子序列

int m,n;

char *x,*y;

int **b,**c;

void LCSLength(int m,int n,char *y,char *x,int **c,int **b); void LCS(int i,int j,char *x,int**b);

cout<<"请输入两个序列的长度："<<endl;

cin>>m>>n;

x=new char[m];

y=new char[n];

cout<<"请输入两个序列："<<endl;

cin>>x>>y;

b=new int *[m + 1];

for (int i=0;i<=m;i++)

b[i]=new int[n + 1];

c=new int *[m + 1];

for (int j=0;j<=m;j++)

c[j]=new int[n + 1];

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

cout<<"最长公共子序列的元素个数为"<<c[m][n]<<endl;

cout<<"该序列为:";

LCS(m,n,x,b);

cout<<endl;

return 0;

}

4运行结果

请输入两个序列的长度：

5

5

请输入两个序列：

dfdhh

dfdgh

最长公共子序列的元素个数为4

该序列为:dfdh

Press any key to continue

本文来源：https://www.bwwdw.com/article/yow1.html