




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、 公共子序列问题 徐康一算法设计 假设有两个序列X和Y,假设X和Y分别有m和n个元素,则建立一个二维数组C(m+1)*(n+1),记录Xi与Yj的LCS的长度。将Ci,j分为三种情况: 若i =0 或j =0时,Ci,j=0; 若i,j0且Xi=Yj,Ci,j=Ci-1,j-1+1; 若i,j0且XiYj,Ci,j=maxCi-1,j,Ci,j-1。 再使用一个m*n的二维数组b,bi,j记录Ci,j的来向: 若Xi=Yj,则Bi,j中记入“”,记此时bi,j = 1; 若XiYj且Ci-1,j Ci,j-1,则bi,j中记入“”,记此时Bi,j = 2; 若XiYj且Ci-1,j Ci,j-
2、1*/ LCS_Output(b,X,i-1,j) else if bi,j=3 then /*XiYj且Ci-1,jCi,j-1*/ LCS_Output(b,X,i,j-1) else if bi,j=4 then /*XiYj且Ci-1,j=Ci,j-1*/ LCS_Output(b,X,i-1,j) LCS_Output(b,X,i,j-1) 2 算法时间复杂度分析 由上述对算法的分析得知,求辅助数组C和B所消耗的时间复杂度为O(mn),而查找所有的公共子序列的时间复杂度取决于所遍历的路径,而路径是由算法递归的方向决定的。显然,最好的情况是m=n并且B中的所有值都为1(按斜对角线方向搜
3、索),此时时间复杂度为O(n)。当X和Y序列不存在公共子序列时为算法的最坏情况,因为此时C数组的所有元素都为0,B在每一个节点都要沿着两个不同的方向搜索,即每次都要调用两次LCS_Output,当调用到i=0或j=0时返回,直到搜索完整个m*n数组才结束。该时间复杂度就是计算从点(m,n)到i=0或j=0的所有路径。建立如上图的直角坐标系,设点S(m,n),轴上的坐标点P1(1,0) 到Pm(m,0),轴上的系列坐标点Q1(0,1) 到Qn(0,n)。因为是搜索路径的边界上的点,点不能直接到达点,点也不能直接到达,所以点到和的路径数等价于到点和点的路径数,又因为点到路径数为,设总路径数为,则有
4、3 程序流程图如下所示4 程序源码package Homework2;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.HashSet;import java.util.Set;public class LCS int C;int B;Set LCS_SET = new HashSet(); /使用集合去重public int LCSLength(char X, char Y) /返回公共子序列长度int m = X.length;
5、int n = Y.length;C = new intX.lengthY.length;B = new intX.lengthY.length;for (int i = 0; i m; i+) Ci0 = 0;Bi0 = 0;for (int j = 0; j n; j+) C0j = 0;B0j = 0;for (int i = 1; i m; i+) for (int j = 1; j Cij - 1) Cij = Ci - 1j;Bij = 2; else if (Ci - 1j Cij - 1) Cij = Cij - 1;Bij = 3; else Cij = Ci - 1j;Bi
6、j = 4;return Cm - 1n - 1;public void LCS_Output(int Direction, char X, int i, int j, int len,char LCS) int lcslen = len;if (i = 0 | j = 0) LCS_SET.add(String.valueOf(LCS);return;if (Bij = 1) LCSlen - 1 = Xi;len-;LCS_Output(B, X, i - 1, j - 1, len, LCS); else if (Bij = 2) LCS_Output(B, X, i - 1, j, l
7、en, LCS); else if (Bij = 3) LCS_Output(B, X, i, j - 1, len, LCS); else if (Bij = 4) LCS_Output(B, X, i - 1, j, len, LCS);LCS_Output(B, X, i, j - 1, len, LCS);/* * param args */public static void main(String args) throws IOException / TODO Auto-generated method stubchar X, Y;BufferedReader buf = null
8、;buf = new BufferedReader(new InputStreamReader(System.in);System.out.println(请输入一个序列);X = buf.readLine().toCharArray();char X_temp = new charX.length + 1;for (int i = 0; i X.length; i+) X_temp0 = ;X_tempi + 1 = Xi;System.out.println(请输入一个序列);Y = buf.readLine().toCharArray();char Y_temp = new charY.
9、length + 1;for (int i = 0; i Y.length; i+) Y_temp0 = ;Y_tempi + 1 = Yi;System.out.print(X=);for (char x : X) System.out.print(x);System.out.println();System.out.print(Y=);for (char y : Y) System.out.print(y);System.out.println();LCS lcs = new LCS();int len = lcs.LCSLength(X_temp, Y_temp);char LCS = new charlen;int m = X.length;int n = Y.length;System.out.println(最长公共子序列长度为: + len); / 输出最长子序列长度System.out.print(最长公共子序列有:);lcs
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年辅警招聘考试综合提升试卷含答案详解(培优b卷)
- (2025)辅警招聘考试试题库及答案详解(必刷)
- 2022年2月韶关市税务系统遴选面试真题附详解
- 2022年2月锦州市税务系统遴选面试真题带详解
- 2022年11月三门峡市直遴选面试真题附解析
- 2025年行政执法基础知识综合练习题及答案详解(考点梳理)
- 2024年甘肃陕煤集团韩城煤矿招聘笔试真题完整答案详解
- 2011年会计从业资格考试试题及答案
- 19数独题目及答案
- 5s与目视化管理考试试题及答案
- 23《祖先的摇篮》(教学设计)2023-2024学年统编版语文二年级下册
- 2024年深圳市烟草专卖局招聘笔试真题
- 齐鲁名校大联考2025届山东省高三第七次学业水平联合检测语文试题及答案
- 外科肛肠科试题及答案
- 骨科围手术期的疼痛护理
- 子宫颈炎护理查房
- 严重过敏反应诊断和临床管理专家共识(2025年版)解读
- 中国2型糖尿病运动治疗指南(2024版)解读 2
- 北师大版五年级数学下册典型例题第六单元:确定位置和描述路线专项练习(原卷版+解析)
- 旱地划龙舟课件
- 中医院面试题及答案
评论
0/150
提交评论