求最长公共子子序列 - armstelang的博客

作者在 2011-12-17 22:16:22 发布以下内容

#include <iostream>
#include <string>
using namespace std;
//主函数
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]; // 注意这里，原式没有+1
for (int i=0;i<=m;i++)
  b[i]=new int[n + 1]; // 注意这里，原式没有+1
c=new int *[m + 1];
for (int j=0;j<=m;j++)
  c[j]=new int[n + 1]; // 注意这里，原式没有+1
LCSLength(m,n,x,y,c,b);
cout<<"最长公共子序列的元素个数为"<<c[m][n]<<endl;
cout<<"该序列为:";
LCS(m,n,x,b); //注意后面的内容是清理，暂时先跳过去，你先搞定主程序先
/* delete []x;
delete []y;
for(int k=0;k<=m;k++)
  delete []b[k];
delete []b;
for(int h=0;h<=m;h++)
  delete []c[h];
delete []c;
*/
return 0;
}
//计算最优值
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);
}