最长公共子序列毕业论文

// 求LCS的长度class LCS{public: LCS(int nx, int ny, char *x, char*y); //创建二维数组c、s和一维数组a、b，并进行初始化 void LCSLength(); //求最优解值（最长公共子序列长度） void CLCS(); //构造最优解（最长公共子序列） ……private: void CLCS(int i, int j); int **c, **, n; char *a, *b;};int LCS::LCSLength() { for(int i=1; i<=m; i++) c[i][0]=0; for(i=1; i<=n; i++) c[0][i]=0; for (i=1; i<=m; i++) for (int j=1; j<=n; j++) if (x[i]==y[j]){ c[i][j]=c[i-1][j-1]+1; s[i][j]=1; //由c[i-1][j-1]计算c[i][j] } else if (c[i-1][j]>=c[i][j-1]){ c[i][j]=c[i-1][j]; s[i][j]=2; //由c[i-1][j]得到c[i][j] } else { c[i][j]=c[i][j-1]; s[i][j]=3; //由c[i][j-1]得到c[i][j] } return c[m][n]; //返回最优解值} // 构造最长公共子序列void LCS::CLCS(int i, int j){ if (i==0||j==0) return; if (s[i][j]==1){ CLCS(i-1, j-1); cout<

#include #include using namespace std;#define N 100 // 宏定义N的初始值为100char a[N], b[N], str[N]; //a用于保存第一个输入的字符的，b用于保存第二个，str用于判断两个字符是不是都遍历到了'\0'(到了的话说明字符串处理完毕)，先初始化为Nint c[N][N]; //int型数组，初始化为N，用于保存两个字符串的内容 //下面你要跟着程序的调用规律走，先看主函数调用的是build_lcs(),然后是lcs_len()int lcs_len(char* a, char* b,int c[][N]) //用于计算两个字符串的每个元素的内容！{ int m=strlen(a), n=strlen(b), i, j; //声明m，n，i,j变量,其中的strlen()函数是用来获取字符串长度的 for (i=0; i<=m; i++) // c[i][0]=0; //遍历第一个字符串的内容，分别保存到c的一维数组中 for (i=0; i<=n; i++) // c[0][i]=0; //遍历第二个字符串的内容，分别保存到c的二维数组中 for (i=1; i<=m; i++) //第一层FOR循环 { // for (j=1; j<=n; j++) //第二层FOR循环 { // // if (a[i-1]==b[j-1]) //判断第一个字符串的第i(-1是为了去掉'\0')个元素的值等于第二个字符串第j个元素 c[i][j]=c[i-1][j-1]+1; // else if (c[i-1][j]>=c[i][j-1]) //如果不是，则判断第一个字符数组的第i个元素与第二个字符数组所有元素相等(j循环j遍,i才循环1遍) c[i][j]=c[i-1][j]; // else //如果不是，则判断第一个字符数组的第j个元素与第二个字符数组所有元素相等(i循环j遍,j才循环1遍) c[i][j]=c[i][j-1]; // } // } // return c[m][n]; //得到相同的元素并返回}char* build_lcs(char s[],char* a,char* b) { int i=strlen(a), j=strlen(b); int k=lcs_len(a,b,c); s[k]='\0'; while (k>0) //下面都很简单了！ { if (c[i][j]==c[i-1][j]) i--; else if (c[i][j]==c[i][j-1]) j--; else { s[--k]=a[i-1]; i--; j--; } } cout<>a; cin>>b; cout<<"LCS="<