2022年找出所有的最长公共序列收集 .pdf

动态规划：找出所有的LCS用动态规划法求解问题特性：a. 具有重叠性 ;b. 具有最优子结构性质1. 最长公共子序列 (LCS)的概念：若 ZX，ZY，且不存在比Z 更长的 X和 Y 的公共子序列，则称 Z 是 X和 Y 的最长公共子序列，记为Z LCS(X , Y)。最长公共子序列往往不止一个。e.g. X=, Y=, 则Z=, Z=, Z =均属于 LCS(X , Y) ，即 X,Y 有 3 个 LCS 。2. 寻找最长公共子序列由书上分析结果：（ 1）若 xm=yn，则问题化归成求Xm-1与 Yn-1的 LCS（ LCS(X , Y)的长度等于LCS(Xm-1 , Yn-1) 的长度加1）（ 2）若 xmyn则问题化归成求Xm-1与 Y的 LCS及 X与 Yn-1的 LCS LCS(X , Y)的长度为：maxLCS(Xm-1 , Y)的长度 , LCS(X , Yn-1) 的长度 3. 求取最长公共子序列引进一个二维数组C，用 Ci,j记录 Xi与 Yj的 LCS的长度如果我们是自底向上进行递推计算，那么在计算Ci,j之前，Ci-1,j-1, Ci-1,j与 Ci,j-1均已计算出来。此时我们根据 Xi=Yj还是 XiYj，就可以计算出Ci,j：若 Xi=Yj，则执行 Ci,j Ci-1,j-1+1；若 XiYj ，则根据：Ci-1,jCi,j-1，则 Ci,j取 Ci-1,j；否则 Ci,j取 Ci,j-1。即有Ci,j=e.g. 如下图： 0 1 2 3 4 5 6yj B D C A B A0 xi 0 0 0 0 0 0 01 A 0 0 0 0 1 1 12 B 0 1 1 1 1 2 23 C 0 1 1 2 2 2 2名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 4 B 0 1 1 2 2 3 3 5 D 0 1 2 2 2 3 36 A 0 1 2 2 3 3 47 B 0 1 2 2 3 4 4为了搜索到所有的LCS的，使用一个m n 的二维数组b，bi,j记录 Ci,j是通过哪一个子问题的值求得的,以决定搜索的方向：若 Ci-1,jCi,j-1，则 bi,j中记入“”；若 Ci-1,jCi,j-1时，则 bi,j中记入“”，若 Ci-1,j Ci-1,j要执行 bi,j=“”，XiYj且 Ci,j-1 Ci,j-1 then Ci,jCi-1,j； bi,j“”； else if Ci-1,j=Ci,j-1 then Ci,jCi-1,j； bi,j“”；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - elseCi,jCi,j-1； bi,j“”； 算法的时间复杂度显然是(mn) 的。4 程序如下：/ 输出 LCS.cpp#include#include#include#include#include#includeusing namespace std;/*寻找最长公共子序列*/void LCS_L(int X,int Y,intm,intn,int C10,char D10)inti,j,k,l;for(i=0;i=m;i+) /给数组 C 、D边界赋值Ci0=0;Di0=0; /i=0时取值为0for(j=0;j=n;j+)C0j=0;D0j=0; /j=0时取值为0for(i=1;i=m;i+) /获取 Cij的值for(j=1;jCij-1)/比较大小求取C、 D两数组的对应值Cij=Ci-1j;Dij=;else if(Ci-1j=Cij-1)Cij=Ci-1j;Dij=;elseCij=Cij-1;Dij=;coutendl输出二维数组bendl;for(k=0;k=10;k+) /输出二维数组bfor(l=0;l=9;l+)coutDkl ;coutendl;/ 调用显示最长公共子序列函数/*输出一个最长公共子序列*/void LCS_OutputOne(int C10,int X,int Y,inti,int j)if(i=0|j=0)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - coutendlAn LCSLength string: ;return; /到边界是返回if(Xi-1=Yj-1) /bij=$LCS_OutputOne(C,X,Y,i-1,j-1); /对角线查找coutCij-1)LCS_OutputOne(C,X,Y,i-1,j); / bij=else if(Ci-1jCij-1)LCS_OutputOne(C,X,Y,i,j-1); /bij=elseLCS_OutputOne(C,X,Y,i,j-1); /bij=/*输出所有最长公共子序列*/void LCS_OutputAll(int C10,char D10,int X,inti,intj,int Result,intlen,int k)if(i=0 | j=0)/到边界时返回int n;for(n=0;nk;n+)coutResultn; /输出数值 cout)/向上走LCS_OutputAll(C,D,X,i,j-1,Result,len,k);else if(Dij=)/向左走LCS_OutputAll(C,D,X,i-1,j,Result,len,k);elseLCS_OutputAll(C,D,X,i,j-1,Result,len,k);LCS_OutputAll(C,D,X,i-1,j,Result,len,k);/*主函数 */int main()inti,j,k,x,y;intlen=0;int A10=0;int B9=0;int C1110=0;char D1110=0;system(color FC);srand(time(0);cout 数组 A:;for(i=0;i10;i+)/名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - Ai=rand()%3;coutAi ;coutendl数组 B:;for(j=0;j9;j+)/Bj=rand()%3;coutBj ;LCS_L(A,B,10,9,C,D);/cout 显示二维数组Cendl;for(i=0;i11;i+) /显示二维数组Cfor(j=0;j10;j+)coutCij ;coutendl;len=Ci-1j-1;/x=10;y=9;k=len;int Resultlen;coutendllcs长度为： len;LCS_OutputOne(C,A,B,x,y);coutendlendl;cout 所有的 Lcs 如下 :endl;LCS_OutputAll(C,D,A,x,y,Result,len,k);coutendl结束 ;return 0;5. 结果分析：由 LCS_Output_All函数可知，求出所有的LCS的长度就是根据数组bij中的值，即搜索的方向信息来遍历所有可能的路径找到满足条件的元素集合。函数 LCS_L的时间复杂度是求解数组b 和 c 的执行时间，是O(mn+m+n) 。而函数LCS_Output_All的时间复杂度取决于遍历的路径数。在最好的情况下，即X序列和 Y序列完全相等，m=n ，数组 b 中的值都名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 是 $（指向对角线方向），所以时间复杂度是O(m)。而在最坏情况下，即X序列和 Y序列不存在公共子序列，数组b 中的值都是“ 4”，就是要分别沿向上和向左的方向搜索，这是每处理一次Xi和 Yj，都必须沿着两个方向调用函数LCS_Output_All ，当遇到 i=0 或j=0 的情况开始返回，只有在搜索完所有的路径后算法才结束。要确定最坏情况的时间复杂度，就是要计算出从点(m,n) 到 i=0 或 j=0 （除 (i,j)=（0，0）外）的所有路径。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -