1 #include <cstdlib> 2 #include <iostream> 3 #include <cstring> 4 5 using namespace std; 6 7 class maxlen_string 8 { 9 public: 10 void string_(); 11 void LCSLength(int,int,char*,char*,int**,int**); 12 void LCS(int,int,char*,int**); 13 ~maxlen_string(){} 14 }; 15 16 17 18 void maxlen_string::LCSLength(int m,int n,char* x,char* y,int**c,int**b) 19 { 20 int i,j; 21 for(i=1;i<=m;i++) c[i][0]=0; 22 for(i=1;i<=n;i++) c[0][i]=0; 23 for(i=1;i<=m;i++) 24 for(j=1;j<=n;j++) 25 { 26 if(x[i]==y[j]) {c[i][j]=c[i-1][j-1]+1;b[i][j]=1;} 27 else if(c[i-1][j]>=c[i][j-1]) {c[i][j]=c[i-1][j];b[i][j]=2;} 28 else {c[i][j]=c[i][j-1];b[i][j]=3;} 29 } 30 } 31 32 void maxlen_string::LCS(int i,int j,char* x,int**b) 33 { 34 if(i==0||j==0) return; 35 if(b[i][j]==1) {LCS(i-1,j-1,x,b);std::cout<<x[i];} 36 else if(b[i][j]==2) LCS(i-1,j,x,b); 37 else LCS(i,j-1,x,b); 38 } 39 40 void maxlen_string::string_() 41 { 42 char x[1000],y[1000]; 43 char*x_=x;char*y_=y; 44 x_++;y_++; 45 x[0]='a';y[0]='b'; 46 47 cout<<"Please input sting 1:"<<std::endl; 48 cin>>x_; 49 cout<<"Please input sting 2:"<<std::endl; 50 cin>>y_; 51 int m=strlen(x); 52 int n=strlen(y); 53 int**c;int**b; 54 c=new int*[m+1];b=new int*[m+1]; 55 for(int i=0;i<=m;++i) 56 { c[i]=new int[n+1];b[i]=new int[n+1];} 57 LCSLength(m,n,x,y,c,b); 58 cout<<"the max length of commen substring is:"<<endl; 59 LCS(m,n,x,b); 60 } 61 62 63 int main(int argc, char *argv[]) 64 { 65 maxlen_string aa; 66 aa.string_(); 67 system("PAUSE"); 68 return EXIT_SUCCESS; 69 }
example：
