最长公共子序列LCS.docVIP

求解所有最长公共子序列LCS_LENGTH，完成的功能是计算数组B和C。具体过程是：先是动态申请二维数组B和C，他们的行列长度都增加1，目的就是方便计算。将C的第0行和第0列都赋上0，即初始化。开始计算C[i][j]，以行为主，一次计算C的每一个元素，即将两个数组逐一比较。比较时就有两种情况，分别是若相等时，就将C[i][j]设置成C[i-1][j-1]，同时将B[i][j]设置成DIAGONAL。若不相等时，比较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]设置为UP_LEFT；二是若C[i-1][j] 大于 C[i][j-1]，则将C[i-1][j]赋给C[i][j]，并且将B[i][j]设置成UP；最后是若C[i-1][j] 小于 C[i][j-1]，则将C[i][j-1]赋给C[i][j]，并且将B[i][j]设置成LEFT。 根据第 3）步骤的结果，就可以找出所有LCS了。这里会用到回溯方法，具体实现可以用栈，也可以用递归。本人使用的是递归，代码简单、易懂。具体实现方法是：申请一个数组用于保存一个LCS，这个数组会反复使用，因此，一旦找到一个就会立即将它输出。再设置一个变量curpos标识当前的数组下标，一个变量len保存当前LCS数组的元素个数。扫描二维数组B，从最后一个开始，判断B的值，有四种情况：当B的值是UP时，就向上递归；当B的值是LEFT时，就向左递归；当B的值是向上或是向左时，这是存在两个选择，先左后上，或是先上后左；当B的值是对角线的时，此时LCS数组才保存当前的字符，len加1，继续沿对角线递归，递归完之后，len减1，回溯。若len为LCS的长度时，就输出。 算法流程图 功能函数LCS_LENGTH的流程图  图 1功能函数Print_LCS的流程图 图 2 测试结果 测试用例保存在LCS.in的文件中，如下图3： 图 3 从图3中可以看出，有三组测试用例。本程序运行的结果如图4所示： 图 4 分析结果 从实验的三组测试用例可以看出：第一组是课本上的例子，结果正确；第二组是个反例，没有公共子序列，结果也正确；第三组是生物的应用，即从某种生物上摘取的DNA序列，结果出现三个重复的序列。其实算法是正确的，但是原比较的字符串中重复的字符比较多，如果对每个重复的字符标记不一样，那么所求的结果中不会出现相同的LCS。这也是本实验中的不足——没有检验LCS重复性。故实验中可以加入检测有无重复的LCS程序，但这并不是本实验的重点。 附录（源代码） #include iostream #include cstring #include fstream #include vector #include iterator using namespace std; int **C,**B;//C保存计算Xi和Yi的LCS值；B保存当前的C是从哪个子问题得来的 char *LCS;//保存一个最长公共子序列 int len = 0;//回溯时用到的统计保存LCS数组当前长度 enum {DIAGONAL,UP,LEFT,UP_LEFT}; //定义方向，分别是：对角线、向上、向左和向左向上 /*LCS_LENGTH函数，求出数组C和B*/ void LCS_LENGTH(vector char X,vector char Y,int m, int n)//计算C { C = new int*[m];//动态分配二维数组 B = new int*[m]; for(int i = 0; i m; i++) { C[i] = new int[n]; B[i] = new int[n]; } for(i = 1;i m;i++)//赋初值，第0列 C[i][0] = 0; for(int j = 0;j n;j++)//第0行 C[0][j] = 0; for(i = 1;i m;i++)//开始计算 { for (j = 1;j n;j++) { if(X.at(i-1) == Y.at(j-1))//此下标与数组的下标差1，相等时 { C[i][j] = C[i-1][j-1] +1;//左上角的LCS+1 B[i][j] = DIAGONAL; } else //不相等 { if(C[i-1][j] == C[i][j-1])//up和left { C[i][j] = C[i-1][j]; B[i][j] = UP_LEFT; }