最长公共子序列lcs

《最长公共子序列lcs》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、求解所有最长公共子序列一、问题分析该部分思路同课件二、算法设计思路根据问题分析的结果，具体的算法设计思路如下：1)申明两个数组，用于保存比较的两个字符串；由于事先不知字符串大小，故动态的实现，这里用C++的容器。2)申明全局变量，二维数组B和数组C。数组C用于保存计算Xi和Yi的LCS值；数组B保存当前的C是从哪个子问题得来的。为此，定义一个枚举类型，用于标识不同的方向，分别为对角线、向上、向左和向左向上四个方向。3)根据动态规划，实现一个函数LCS_LENGTH，完成的功能是计算数组B和C。具体过程是：先是动态申请二维数组B和C，他们的行列长

2、度都增加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[

3、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。4)根据第3）步骤的结果，就可以找出所有LCS了。这里会用到回溯方法，具体实现可以用栈，也可以用递归。本人使用的是递归，代码简单、易懂。具体实现方法是：申请一个数组用于保存一个LCS，这个数组会反复使用，因此，一旦找到一个就会立即将它输出。再设置一个变量curpos标识当前的数组下标，一个变量len保存当前LCS数组的元素个数。扫描二维数组B，从最后一个

4、开始，判断B的值，有四种情况：当B的值是UP时，就向上递归；当B的值是LEFT时，就向左递归；当B的值是向上或是向左时，这是存在两个选择，先左后上，或是先上后左；当B的值是对角线的时，此时LCS数组才保存当前的字符，len加1，继续沿对角线递归，递归完之后，len减1，回溯。若len为LCS的长度时，就输出。三、算法流程图1.功能函数LCS_LENGTH的流程图8否大于相等相等是是开始动态申请二维数组Ｂ和Ｃ，行为ｍ，列为ｎ将Ｃ的第０行与第０列赋初值０ｉ＝　１ｊ＝　１不相等小于否ｉ＜ｍ？ｊ＜ｎ？当前比较的两个字符相等吗？C[i][j]=C[i-1

5、][j-1]+1;B[i][j]=DIAGONAL;C[i-1][j]与C[i][j-1]相等吗？C[i][j]=C[i-1][j];B[i][j]=UP_LEFT;C[i][j]=C[i-1][j];B[i][j]=UP;C[i][j]=C[i-1][j];B[i][j]=LEFT;结束图181.功能函数PRINT_LCS的流程图DIAGONALUP_LEFTLEFTUP否是LEFTUPDIAGONAL否是结束开始i=m；j=n；len=0i>=0&&j>=0吗？Len等于LCS长度吗？输出一个LCSB[i][j]的值是？LCS[curpos

6、]=X[i-1];len++;递归i-1,j-1len--;递归j-1递归i-1递归j-1递归i-1图28一、测试结果测试用例保存在LCS.in的文件中，如下图3：图3从图3中可以看出，有三组测试用例。本程序运行的结果如图4所示：图4二、分析结果从实验的三组测试用例可以看出：第一组是课本上的例子，结果正确；第二组是个反例，没有公共子序列，结果也正确；第三组是生物的应用，即从某种生物上摘取的DNA序列，结果出现三个重复的序列。其实算法是正确的，但是原比较的字符串中重复的字符比较多，8如果对每个重复的字符标记不一样，那么所求的结果中不会出现相同的L

7、CS。这也是本实验中的不足——没有检验LCS重复性。故实验中可以加入检测有无重复的LCS程序，但这并不是本实验的重点。一、附录（源代码）#include#include#include#include#includeusingnamespacestd;int**C,**B;//C保存计算Xi和Yi的LCS值；B保存当前的C是从哪个子问题得来的char*LCS;//保存一个最长公共子序列intlen=0;//回溯时用到的统计保存LCS数组当前长度enum{

8、DIAGONAL,UP,LEFT,UP_LEFT};//定义方向，分别是：对角线、向上、向左和向左向上/*LCS_LENGTH函数，求出数组C和B*/