最长公共子序列(LCS)定义:
一个数列 S,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。比如数列A = “abcdef”, B = “adefcb”. 那么两个数列的公共子序列是"adef".
最长公共子序列和最长公共子字符串是有区别的,公共子序列里的元素可以不相邻,但是公共子字符串必须是连接在一起的。比如A和B的公共子字符串是“def”。
求解最长公共子序列要用到动态规划的概念。我们用c[i][j]记录X[i]与Y[j] 的LCS 的长度,那么在计算c[i,j]之前,c[i-1][j-1],c[i-1][j]与c[i][j-1]均已计算出来。此时我们根据X[i] = Y[j]还是X[i] != Y[j],就可以计算出c[i][j]。问题的递归式写成:
在经典的算法导论那本书里,文章使用了b[][]来记录c[i,j] 选自于哪一个(从递归式里,我们知道有三个不同的选择),但是,我们可以不借助于数组b而借助于数组c本身临时判断c[i,j]的值是由c[i-1,j-1],c[i-1,j]和c[i,j-1]中哪一个数值元素所确定,原理是通过我们如何选取c[i,j]来决定的。 在代码里面,我们可以看得出,代码行14,15对应打印的代码行31,32, 代码行17对应打印打印行的36到40。
代码如下:
public static int[][] LCS(String str1, String str2) {
int[][] opt = new int[str2.length() + 1][str1.length() + 1];
for (int i = 0; i <= str2.length(); i++) {
opt[i][0] = 0;
}
for (int j = 0; j <= str1.length(); j++) {
opt[0][j] = 0;
}
for (int j = 1; j <= str1.length(); j++) {
for (int i = 1; i <= str2.length(); i++) {
if (str2.charAt(i-1) == str1.charAt(j-1)) {
opt[i][j] = opt[i-1][j-1] + 1;
} else {
opt[i][j] = ( opt[i-1][j] >= opt[i][j-1] ? opt[i-1][j] : opt[i][j-1]);
}
}
}
return opt;
}
public static void print(int[][] opt, String X, String Y, int i, int j) {
if (i == 0 || j == 0) {
return;
}
if (X.charAt(i - 1) == Y.charAt(j - 1)) {
System.out.print(X.charAt(i - 1));
print(opt, X, Y, i - 1, j - 1); // don't put this line before the upper line. Otherwise, the order is wrong.
}else if (opt[i - 1][j] >= opt[i][j]) {
print(opt, X, Y, i - 1, j);
} else {
print(opt, X, Y, i, j - 1);}
}
分享到:
相关推荐
最长公共子序列问题 Java动态规划求解最长公共子序列问题.zip
关于动态规划算法的最长公共子序列的Java代码,帮助了解算法实现过程
由此函数,把序列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),...
LCS 最长公共子序列 用JAVA实现,直接导入可运行,实例可以另外自己定义
最长公共子序列(Longest Common Subsequence, LCS)问题是计算机科学和生物信息学中的一个经典问题。它要求找出两个序列(如字符串、列表或数组)的最长公共子序列,即在两个序列中以相同顺序出现,并且不改变原有...
java算法分析与设计之最长公共子序列问题源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络资源少的...
java解决动态规划中最长公共子序列(longest common sequence)问题
LCS算法的简单java实现,可以一起讨论学习
主要介绍了Java基于动态规划法实现求最长公共子序列及最长公共子字符串,简单描述了动态规划法的概念、原理,并结合实例形式分析了Java使用动态规划法求最长公共子序列以及最长公共子字符串相关实现技巧,需要的朋友...
最长公共子序列问题 基于java实现动态规划求解最长公共子序列问题
22.javathrows声明抛出异常序列.zip22.javathrows声明抛出异常序列.zip22.javathrows声明抛出异常序列.zip22.javathrows声明抛出异常序列.zip22.javathrows声明抛出异常序列.zip22.javathrows声明抛出异常序列.zip22...
字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=“x0,x1,…,xm-1”,序列Y=“y0,y1,…,yk-1”是X的子序列,存在X的一个...
所有最长公共子序列(LCS)——动态规划——Java---所有!!!所有!!!所有!!!
快速排序算法,求最长公共子序列,0-1背包问题的回溯法求解与分支限界法求解,贪心算法的活动安排问题。都是利用JAVA编程语言实现
算法导论中求最长公共子序列Java实现版
最长公共子序列问题