动态规划法求解最长公共子序列(含Java代码)_第1页
动态规划法求解最长公共子序列(含Java代码)_第2页
动态规划法求解最长公共子序列(含Java代码)_第3页
动态规划法求解最长公共子序列(含Java代码)_第4页
动态规划法求解最长公共子序列(含Java代码)_第5页
已阅读5页,还剩4页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论