LCS.rar_visual c

#include"AllLcs.h" #include <iostream> using namespace std; //初始化数组X，Y AllLcs::AllLcs(char* x,char* y) { X=x; Y=y; m=strlen(X); n=strlen(Y); } //求出数组C，b的值 void AllLcs::LCS_L() { //int m=strlen(X); //int n=strlen(Y); //求出数组X,Y的长度 int **C = new int*[m+1];//数组C 数组b int **b = new int*[m+1]; for(int p=0;p<=m;p++){ C[p]=new int[n+1](); b[p]=new int[n+1](); } /*对于数组b 4代表“↖”；1代表“↑”，2代表“←”3代表“←↑” * */ for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(X[i-1]==Y[j-1]) //X[i]=Y[j]的情况 { C[i][j]=C[i-1][j-1]+1; b[i][j]=4; //4代表“↖” } else if(C[i-1][j]>C[i][j-1])//C[i-1][j]>C[i][j-1] { C[i][j]=C[i-1][j]; b[i][j]=1; //1代表“↑” } else if(C[i-1][j]<C[i][j-1])//C[i-1][j]<C[i][j-1] { C[i][j]=C[i][j-1]; b[i][j]=2; //2代表“←” } else //C[i-1][j]<C[i][j-1] { C[i][j]=C[i-1][j]; b[i][j]=3;//3代表“←↑” } } } cout<<" C: "<<endl; for(int p=0;p<=m;p++) //输出数组C { for(int q=0;q<=n;q++) { cout<<C[p][q]<<" "; } cout<<endl; } cout<<" b: "<<endl; for(int p=0;p<=m;p++) //输出数组b { for(int q=0;q<=n;q++) { cout<<b[p][q]<<" "; } cout<<endl; } cout<<endl; cout<<"The LCS is :"; LCS_output(m,n,b); //调用LCS_output函数求出LCS } //输出 void AllLcs::LCS_output(int i, int j, int** b) { if(i==0||j==0) { cout<<endl; for(int a=store.size()-1;a>=0;a--) { cout<<store[a];//输出 } return; } if(b[i][j]==4) { store.push_back(X[i-1]); //当X[i]=Y[j]的时候存入 LCS_output(i-1,j-1,b); store.pop_back(); } else if(b[i][j]==1) { LCS_output(i-1,j,b);} else if(b[i][j]==2) { LCS_output(i,j-1,b);} else if (b[i][j]==3) { LCS_output(i,j-1,b); LCS_output(i-1,j,b); } }