最长公共子序列LCS.docVIP

求求解解所所有有 最最长长公公共共子子序序列列 一一、问问题题分分析析 该部分思路同课件 二二、算算法法设设计计思思路路 根据问题分析的结果，具体的算法设计思路如下： 1)申明两个数组，用于保存比较的两个字符串；由于事先不知字符串大小，故动态 的实现，这里用 C+的容器。 2)申明全局变量，二维数组 B 和数组 C。数组 C 用于保存计算 Xi 和 Yi 的 LCS 值； 数组 B 保存当前的 C 是从哪个子问题得来的。为此，定义一个枚举类型，用于标 识不同的方向，分别为对角线、向上、向左和向左向上四个方向。 3)根据动态规划，实现一个函数 LCS_LENGTH，完成的功能是计算数组 B 和 C。具 体过程是：先是动态申请二维数组 B 和 C，他们的行列长度都增加 1，目的就是 方便计算。将 C 的第 0 行和第 0 列都赋上 0，即初始化。开始计算 Cij，以行 为主，一次计算 C 的每一个元素，即将两个数组逐一比较。比较时就有两种情况， 分别是若相等时，就将 Cij设置成 Ci-1j-1，同时将 Bij设置成 DIAGONAL。若不相等时，比较 Ci-1j 和 Cij-1的值，又有三种情况：一是 Ci-1j 与 Cij-1相等， 就随便把某一个赋给 Cij，比如 Ci-1j，Bij设 置为 UP_LEFT；二是若 Ci-1j 大于 Cij-1，则将 Ci-1j赋给 Cij，并且将 Bij设置成 UP；最后是若 Ci-1j 小于 Cij-1，则将 Cij-1赋给 Cij，并 且将 Bij设置成 LEFT。 4)根据第 3）步骤的结果，就可以找出所有 LCS 了。这里会用到回溯方法，具体实 现可以用栈，也可以用递归。本人使用的是递归，代码简单、易懂。具体实现方 法是：申请一个数组用于保存一个 LCS，这个数组会反复使用，因此，一旦找到 一个就会立即将它输出。再设置一个变量 curpos 标识当前的数组下标，一个变量 len 保存当前 LCS 数组的元素个数。扫描二维数组 B，从最后一个开始，判断 B 的值，有四种情况：当 B 的值是 UP 时，就向上递归；当 B 的值是 LEFT 时，就 向左递归；当 B 的值是向上或是向左时，这是存在两个选择，先左后上，或是先 上后左；当 B 的值是对角线的时，此时 LCS 数组才保存当前的字符，len 加 1， 继续沿对角线递归，递归完之后，len 减 1，回溯。若 len 为 LCS 的长度时，就输 出。 三三、算算法法流流程程图图 1.功功能能函函数数 LCS_LENGTH 的的流流程程图图 否 大 于 相 等 相 等 是 是 开 始 动态申请二维数组 和，行为，列为 将的第行与 第列赋初值 不 相等 小 于 否 ？ ？ 当前比较的当前比较的 两个字符相等吗？两个字符相等吗？ Cij = Ci-1j-1 +1; Bij = DIAGONAL; Ci-1j 与与 Cij-1相等吗？相等吗？ Cij = Ci- 1j ; Bij =UP_LEFT; Cij = Ci- 1j ; Bij =UP; Cij = Ci- 1j ; Bij =LEFT; 结束 图 1 2.功功能能函函数数 PRINT_LCS 的的流流程程图图 L EFT U P DI AGONA L 否 是 结 束 开 始 i= m； j= n； len= 0 i=0 len+; 递归递归 i-1,j-1 len-; 递归递归 j-1 递归递归 i-1 递归递归 j-1 递归递归 i-1 图 2 否 是 U P L EFT UP_L EFT DIAG ONAL 四四、测测试试结结果果 测试用例保存在 LCS.in 的文件中，如下图 3： 图 3 从图 3 中可以看出，有三组测试用例。本程序运行的结果如图 4 所示： 图 4 五五、分分析析结结果果 从实验的三组测试用例可以看出：第一组是课本上的例子，结果正确；第二组是个反 例，没有公共子序列，结果也正确；第三组是生物的应用，即从某种生物上摘取的 DNA 序 列，结果出现三个重复的序列。其实算法是正确的，但是原比较的字符串中重复的字符比 较多，如果对每个重复的字符标记不一样，那么所求的结果中不会出现相同的 LCS。这也 是本实验中的不足没有检验 LCS 重复性。故实验中可以加入检测有无重复的 LCS 程序， 但这并不是本实验的重点。 六六、附附录录（源源代代码码） #include #include #include #include #include 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 X,vector Y,int m, int n)/计算 C C = new int*m;/动态分配二维数组 B = new int*m; for(int i = 0; i Cij-1)/up Cij = Ci-1j; Bij = UP; else/left Cij = Cij-1; Bij = LEFT; /*Print_LCS 函数，打印出所有的 LCS*/ void Print_LCS(int *B,vector X,int i,int j,int curpos,int maxLCS,ostream k = 0;k-) out:iterator beg, vector:iterator end) while(beg != end) cout X, Y; ifstream fin(“LCS.in“);/输入文件 /char XMAXSIZE,YMAXSIZE; int count = 0;/实验的测试组数 coutcount; fin.get(s);/过滤一个换行符 cout“These are “count“ groups to be tested!“endl; for(int z = 1;z = count;z+) while(fin.get(s) while (fin.get(s) cout“The group “z“:“endl; out(X.begin(), X.end(); out(Y.begin(), Y.end(); int m = X.size()+1; int n = Y.size()+1; LCS_LENGTH(X,Y,m,n); int max = Cm-1n-1;/保存 LCS 的长度 if(0 = max)/没有最长公共子序列 cout“There is no Longest Common Subsequence!n“endl; else LCS = new charmax; cout“All the Longest Common Subsequence are:“endl; Print_