动态规划法求最长公共子序列111.cpp

应用动态规划法求解两个字串的最长公共自序列及其长度

#include<iostream.h>
#include<malloc.h>
#include<iomanip.h>
void  LCSLength(int Asize,int Bsize,char *Aarray,char*Barray,int **c,int **b);
void LCS(int i,int j,char*x,int **b);

void main()
{
  int Asize,Bsize;
  char *Aarray,*Barray;
  int p[50][50]={0},q[50][50]={0};
  cout<<"数组A长度:";
	  cin>>Asize;
	  cout<<endl;
  cout<<"数组B长度:";
  cin>>Bsize;
  cout<<endl;
  
  Aarray=(char *)malloc(Asize*sizeof(char));
  Barray=(char *)malloc(Bsize*sizeof(char));
 //初始化数组A
 cout<<"输入字符数组A:";
 for(int i=1;i<Asize+1;i++)
 //if(cin.get=="\n")break;
   cin>>Aarray[i];
   //初始化数组B
 cout<<"输入字符数组B:";
 for( i=1;i<Bsize+1;i++)
 cin>>Barray[i];
   cout<<endl;
 
 //输出原始数组A,B
 cout<<"你输入的原始数组A是:[";
 for(i=1;i<=Asize;i++)
 {
	 cout<<Aarray[i];
 }
 cout<<"]"<<endl;
 cout<<"你输入的原始数组B是:[";
 for(i=1;i<=Bsize;i++)
 {
	 cout<<Barray[i];
 }
 cout<<"]"<<endl;
 int *c[50],*b[50];
for(i=0;i<50;i++)
{
 c[i]=p[i];
 b[i]=q[i];
}
 LCSLength( Asize, Bsize, Aarray,Barray,c,b);
 cout<<"最长公共子序列:";
 LCS( Asize,Bsize ,Aarray,b);
 cout<<endl;
}

void LCSLength(int m,int n,char *x,char*y,int **c,int **b)
{
   int i,j;
   //初始化c[i][j],b[i][j]
   for(i=1;i<=m;i++)
   {
	   c[i][0]=0;
       b[i][0]=0;
   }
   for(i=1;i<=n;i++)
   {
	   c[0][i]=0;
       b[0][i]=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);
 
}