问题描述：
给定两个子序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时，则称Z时X和Y的公共子序列。
1 #include<iostream> 2 using namespace std; 3 4 int const N=81; 5 6 void lcslength(int m,int n,char *x,char *y,int c[][N],int b[][N]) 7 { 8 int i,j; 9 for(i=1;i<=m;i++) c[i][0]=0; 10 for(i=1;i<=n;i++) c[0][i]=0; 11 for(i=1;i<=m;i++) 12 for(j=1;j<=n;j++) 13 { 14 if(x[i]==y[j]) 15 { 16 c[i][j]=c[i-1][j-1]+1; 17 b[i][j]=1; 18 } 19 else if(c[i-1][j]>c[i][j-1]) 20 { 21 c[i][j]=c[i-1][j]; 22 b[i][j]=2; 23 } 24 else { 25 c[i][j]=c[i][j-1]; 26 b[i][j]=3; 27 } 28 } 29 } 30 31 void lcs(int i,int j,char *x,int b[][N]) 32 { 33 if(i==0||j==0)return; 34 if(b[i][j]==1) 35 { 36 lcs(i-1,j-1,x,b); 37 cout<<x[i]<<" "; 38 } 39 else if(b[i][j]==2) 40 lcs(i-1,j,x,b); 41 else lcs(i,j-1,x,b); 42 } 43 44 int main() 45 { 46 char x[N],y[N]; 47 int c[N][N],b[N][N]; 48 int m,n; 49 cin>>m; 50 for(int i=1;i<=m;i++) 51 cin>>x[i]; 52 cin>>n; 53 for(int i=1;i<=n;i++) 54 cin>>y[i]; 55 lcslength(m,n,x,y,c,b); 56 lcs(m,n,x,b); 57 return 0; 58 }