#include<stdio.h> #include<iostream> #include<string> using namespace std; int c[10][10]; int b[10][10]; void LCSLength(int m,int n,char *x,char *y,int c[10][10],int b[10][10]){ int i,j; for(i = 0;i <= m;i++) c[i][0] = 0; for(i = 0;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] = 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;} } } void LCS(int i,int j,char *x,int b[10][10]){ if(i == 0|| j == 0) return; if(b[i][j] == 1){ LCS(i-1,j-1,x,b); printf("%c ",x[i]); } else if(b[i][j] == 2) LCS(i-1,j,x,b); else LCS(i,j-1,x,b); } void main(){ int m,n; printf("输入X和Y中的元素数目:"); scanf("%d %d",&m,&n); char *x ; x = (char*)malloc((m+1) * sizeof(char)); char *y; y = (char*)malloc((n+1) * sizeof(char)); printf("输入X中的元素:"); for(int i = 1;i <= m;i++) cin>>x[i]; printf("输入Y中的元素:"); for(i = 1;i <= n;i++) cin>>y[i]; printf("公共子序列为:"); LCSLength(m,n,x,y,c,b); LCS(m,n,x,b); printf("\n长度为%d\n",c[m][n]); free(x); free(y); }