LCS.rar_LCS

#include <iostream> #include <vector> #define MAX 150 using std::cout; using std::cin; using std::vector; using std::endl; //A,B为两个序列，m,n分别为两个序列的长度，c存放最优解值，b为解矩阵 void LCS_length(vector<int> A,vector<int> B,int m,int n,int c[MAX][MAX],int b[MAX][MAX]) { int i,j; for(i=0;i<=m;i++) c[i][0]=0; for(j=0;j<=n;j++) c[0][j]=0; //b[i][j]=10时c[i, j]由c[i, j-1]确定 //b[i][j]=20时c[i, j]由c[i-1, j-1]确定 //b[i][j]=30时c[i, j]由c[i-1, j]确定 for(i=1;i<=m;i++) for(j=1;j<=n;j++) { if(A[i-1]==B[j-1]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=20; } else { if(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=30; } else { c[i][j]=c[i][j-1]; b[i][j]=10; } } } } void print_LCS(int bb[MAX][MAX],vector<int> x,int a,int b) { if(a==0||b==0) return; if(bb[a][b]==20) { print_LCS(bb,x,a-1,b-1); cout<<" "<<x[a-1]; } else if(bb[a][b]==30) print_LCS(bb,x,a-1,b); else print_LCS(bb,x,a,b-1); } void main () { int xLength=0,yLength=0; vector<int> X; vector<int> Y; int data; cout<<"请输入X序列，输入元素为正整数！输入99999时表示输入结束！"<<endl; cin>>data; while(data!=99999) { X.push_back(data); xLength++; cin>>data; } cout<<"请输入Y序列，输入元素为正整数！输入99999时表示输入结束！"<<endl; cin>>data; while(data!=99999) { Y.push_back(data); yLength++; cin>>data; } cout<<"X序列的元素个数为"<<xLength<<endl; cout<<"Y序列的元素个数为"<<yLength<<endl; int cmatrix[MAX][MAX]; int bmatrix[MAX][MAX]={0}; LCS_length(X,Y,xLength,yLength,cmatrix,bmatrix); cout<<"X,Y的最大公共子序列"<<endl; print_LCS(bmatrix,X,xLength,yLength); }