题目
如果字符串1中的所有字符都按顺序的出现在字符串2中,那么称字符串1是字符串2的子串。现在给定两个字符串,求它们的最长公共子串。
例如:对于字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串,长度为4。
思路
考虑字符串X = {x1, x2, ... xm} 和 Y = {y1, y2, ... yn},记 Z = {z1, z2, ... zk} 为 X 和 Y 的任意一个LCS。
- 如果 xm = yn,那么 zk = xm = yn 而且 Zk-1 是 Xm-1 和 Yn-1 的一个LCS。
- 如果 xm ≠ yn,那么 zk ≠ xm 蕴含 Z 是 Xm-1 和 Y 的一个LCS。
- 如果 xm ≠ yn,那么 zk ≠ yn 蕴含 Z 是 X 和 Yn-1 的一个LCS。
那么如果要求 X 和 Y 的一个LCS,先看如果 xm = yn,则必须找出 Xm-1 和 Yn-1 的一个LCS。将 xm = yn 添加到这个LCS上;如果 xm ≠ yn,就必须找出 Xm-1 和 Y 的一个LCS 以及 X 和 Yn-1 之间的一个LCS。其中较长的就是 X 和 Y 的一个LCS。则有以下递推式。
我们设c[i][j]为 Xi 和 Yj 的一个LCS的长度,那么
- if i < 0 || j < 0, c[i][j] = 0;
- if i, j >= 0 && xi = yj, c[i][j] = c[i-1][j-1] + 1;
- if i, j >= 0 && xi ≠ yj, c[i][j] = max {c[i-1][j], c[i][j-1]};
构造一个LCS
可以使用b[i][j]来记录构造的方向,0表示由Xi-1和Yj-1构造,1表示由Xi-1和Yj构造,2表示由Xi和Yj-1构造。
实现
public class LCS { private int[][] c; private int[][] b; public void lcs(char[] s1, char[] s2) { c = new int[s1.length+1][s2.length+1]; b = new int[s1.length+1][s2.length+1]; for (int i = 0; i <= s1.length; i++) { c[i][0] = 0; } for (int j = 0; j <= s2.length; j++) { c[0][j] = 0; } for (int i = 1; i <= s1.length; i++) { for (int j = 1; j <= s2.length; j++) { if(s1[i-1] == s2[j-1]) { c[i][j] = c[i-1][j-1] + 1; b[i][j] = 0; } else { if (c[i-1][j] >= c[i][j-1]) { c[i][j] = c[i-1][j]; b[i][j] = 1; } else { c[i][j] = c[i][j-1]; b[i][j] = 2; } } } } System.out.println("the lcs is: " + c[s1.length][s2.length]); printSeq(s1, s1.length, s2.length); } public void printSeq(char[] s1, int i, int j) { if (i == 0 || j == 0) return; if (b[i][j] == 0) { printSeq(s1, i-1, j-1); System.out.print(s1[i-1] + " "); } else if (b[i][j] == 1) { printSeq(s1, i-1, j); } else { printSeq(s1, i, j-1); } } public static void main(String[] args) { char[] s1 = {'b','d','c','a','b','a'}; char[] s2 = {'a','b','c','b','d','a','b'}; LCS l = new LCS(); l.lcs(s1, s2); } }
相关推荐
运用动态规划算法解决最长公共子序列问题,计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=, x2, …, xm>和Y=, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与...
最长公共子序列问题就是给定两个序列X={x1,x2,...xm}和Y={y1,y2,...yn},找出X和Y的一个最长公共子序列。 Input 输入包含多组测试数据。第一行为一个整数C,表示有C组测试数据,接下来有C行数据,每组测试数据...
算法工程项目问题描述: 【题目】 动态规划思维训练——最长公共子序列算法的设计与实现 给定两个序列X={X1, X2,···,Xm}和...字符串Y:{ABCBDAB},则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA
最长公共子序列的两种算法简介,一种是平时最常见的算法,还有一种用滚动数组来做的。
最长公共子序列问题 最长公共子序列(动态规划) 实验数据:input.txt X={A,B,C,B,D,A,B}; Y={B,D,C,A,B,A} ——要求给出X、Y的最长公共子序列Z,程序运行结束时,将计算结果输出到文件output.txt中。输出文件中包含...
由此函数,把序列X={x1,x2….xm}和Y={y1,y2…ym}的最长公共子序列的搜索分为M个阶段,第1阶段,按照式1计算X1和Yj的最长公共子序列长度L[1][j](1),第2阶段,按照2式计算X2和Yj的最长公共子序列长度L[2][j](1),...
C++求最长公共子序列!实用 花费了好长时间!!
算法导论实验 最长公共子序列程序源码 实验报告
最长公共子序列的算法实现,采用递归方法。
动态规划的一个计算两个序列的最长公共子序列的方法如下: 以两个序列 X、Y 为例子: 设有二维数组 f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有: f[1][1] = same(1,1); f[i,j] = max{f[i-1...
用Python实现动态规划中最长公共子序列和最长公共子串问题!
最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法
实现了求最长公共子序列的算法,内容简单易懂,代码也很短