LCS.rar_Enjoy_LCS

#include <iostream> using namespace std; #define max(a,b) (((a) > (b)) ? (a) : (b)) int c[100][100]; char b[100][100]; int len = 0; static char k[100]; int O= 0; int LCS(char x[],char y[],int i,int j ) { int c; O++; if(i==-1||j==-1) c = 0; else if(x[i]==y[j]) { c = 1+LCS(x,y,i-1,j-1); k[c] = x[i]; } else { int c1 = LCS(x,y,i,j-1); int c2 = LCS(x,y,i-1,j); c = c1; if(c1<c2) c = c2; } return c; } void LCS1(char x[],char y[],int m,int n) { O= 0; 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++) { O++; if(x[i] == y[j]) c[i][j] = c[i-1][j-1]+1, b[i][j] = '@'; else if(c[i-1][j]>=c[i][j-1]) c[i][j] = c[i-1][j], b[i][j] = '#'; else c[i][j] = c[i][j-1], b[i][j] = '$'; } } void print(char b[][100],char x[],int i,int j) { if(i==0||j==0) return; if(b[i][j]=='@'){ print(b,x,i-1,j-1); cout<<x[i]; } else if (b[i][j]=='#') print(b,x,i-1,j); else print(b,x,i,j-1); } int main() { char x[200]; char y[200]; cin>>x; cin>>y; len = LCS(x,y,strlen(x)-1,strlen(y)-1); cout<<O<<endl; for(int i=1;i<=len;i++) cout<<k[i]; cout<<endl; /* LCS1(x,y,7,6); print(b,x,7,6); cout<<c[7][6]; cout<<O<<endl; */ }