最长公共子序列c++

#include <iostream> using namespace std; #define max 100 void LCS_Length(char *x,char *y,int **b,int m,int n) { int **c; c=new int*[m+1]; for(int i=0;i<m+1;i++) c[i]=new int[n+1]; for(i=0;i<m+1;i++) c[i][0]=0; for(i=0;i<n+1;i++) c[0][i]=0; for(i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(x[i-1]==y[j-1]) { 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; } } } cout<<"这两个字符串最长公共子序列的长度为:"<<c[m][n]<<endl; for(i=0;i<m+1;i++) delete []c[i]; delete []c; } //打印结果 void Print_LCS(int **b,char *x,int i,int j) { if(i==0||j==0) return ; if(b[i][j]==1) { Print_LCS(b,x,i-1,j-1); cout<<x[i-1]; } else if(b[i][j]==2) Print_LCS(b,x,i-1,j); else Print_LCS(b,x,i,j-1); } int main() { char x[max]; char y[max]; cout<<"求解两个字符串序列的最长公共子序列"<<endl<<"输入第一个字符串:"; cin>>x; cout<<endl<<"输入第二个字符串:"; cin>>y; cout<<endl; int m=strlen(x); int n=strlen(y); int **b; b=new int*[m+1]; for( int i=0;i<m+1;i++) b[i]=new int[n+1]; LCS_Length(x,y,b,m,n); cout<<"最长公共子序列为:"; Print_LCS(b,x,m,n); cout<<endl; for(i=0;i<m+1;i++) delete []b[i]; delete []b; return 0; }