最长公共子序列.cpp

利用动态规划算法解决最长公共子序列问题的改进算法。

#include<iostream.h> 
#include<string.h> 
#define max 100          // 定义输入字符串的最大长度
int c[max][max];         // c[i][j] 用来记录x[i],y[j]的最长公共子序列长度
int b[max][max];         // b[i][j] 记录 c[i][j]是由哪个子问题的解得到 2表示c[i-1][j-1],1表示c[i][j-1],-1表示c[i-1][j]

void LCSLength(int m,int n,char*x,char*y)   //计算最长公共子序列长度
{ 
int i,j; 
for(i=1;i<=m;i++)c[i][0]=0;   
for(i=1;i<=n;i++)c[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]=2;// 表示c[i][j]由c[i-1][j-1]得到 
	  } 
      else if (c[i-1][j]>=c[i][j-1]) 
	  { 
        c[i][j]=c[i-1][j]; 
        b[i][j]=1;// 表示c[i][j] 由c[i][j-1]得到
	  } 
           else 
		   { 
             c[i][j]=c[i][j-1]; 
             b[i][j]=-1;// 表示 c[i][j] 由c[i-1][j]得到
		   } 
   } 
} 


void LCS(int i,int j,char *x)  //构造最长公共子序列
{ 
 if(i==0||j==0)  return;   //递归出口 
   if(b[i][j]==2) 
   { 
     LCS(i-1,j-1,x);    
     cout<<x[i]; 
   } 
   else if(b[i][j]==1) LCS(i-1,j,x); 
   else LCS(i,j-1,x); 
} 


void main() 
{ 
int m1,n1;
char *str1,*str2; 
str1=new char[100]; 
str2=new char[100]; 
cout<<"输入第一个字符串"; 
cin>>str1+1; 
cout<<endl<<"输入第二个字符串"; 
cin>>str2+1; 
cout<<endl; 
m1= strlen(str1); 
n1= strlen(str2); 
LCSLength(m1-1,n1-1,str1,str2); 
LCS(m1-1,n1-1,str1); 
return; 
}