2022年找出所有的最长公共序列收集 .pdf
《2022年找出所有的最长公共序列收集 .pdf》由会员分享,可在线阅读,更多相关《2022年找出所有的最长公共序列收集 .pdf(8页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、动态规划:找出所有的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、)( 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
3、,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
4、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“”;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -
5、- 名师精心整理 - - - - - - - 第 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
6、=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(in
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年找出所有的最长公共序列收集 2022 找出 所有 最长 公共 序列 收集
限制150内