动态规划算法之：最长公共子序列 & 最长公共子串（LCS）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了动态规划算法之：最长公共子序列 & 最长公共子串（LCS），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4334字，纯文字阅读大概需要7分钟。
内容图文
1、先科普下最长公共子序列 & 最长公共子串的区别：
找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。
2、最长公共子串
其实这是一个序贯决策问题，可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢？直接举个例子吧："bab"和"caba"(当然我们现在一眼就可以看出来最长公共子串是"ba"或"ab")
b a b
c 0 0 0
a 0 1 0
b 1 0 1
a 0 1 0
我们看矩阵的斜对角线最长的那个就能找出最长公共子串。
不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事，下面改进：当要在矩阵是填1时让它等于其左上角元素加1。
b a b
c 0 0 0
a 0 1 0
b 1 0 2
a 0 2 0
这样矩阵中的最大元素就是 最长公共子串的长度。
在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了，所以实际上在程序中可以用一维数组来代替这个矩阵。
2.1 代码如下：
public class LCString2 {
public static void getLCString(char[] str1, char[] str2) {
int i, j;
int len1, len2;
len1 = str1.length;
len2 = str2.length;
int maxLen = len1 > len2 ? len1 : len2;
int[] max = new int[maxLen];
int[] maxIndex = new int[maxLen];
int[] c = new int[maxLen]; // 记录对角线上的相等值的个数
for (i = 0; i < len2; i++) {
for (j = len1 - 1; j >= 0; j--) {
if (str2[i] == str1[j]) {
if ((i == 0) || (j == 0))
c[j] = 1;
else
c[j] = c[j - 1] + 1;
} else {
c[j] = 0;
}
if (c[j] > max[0]) { // 如果是大于那暂时只有一个是最长的,而且要把后面的清0;
max[0] = c[j]; // 记录对角线元素的最大值，之后在遍历时用作提取子串的长度
maxIndex[0] = j; // 记录对角线元素最大值的位置
for (int k = 1; k < maxLen; k++) {
max[k] = 0;
maxIndex[k] = 0;
}
} else if (c[j] == max[0]) { // 有多个是相同长度的子串
for (int k = 1; k < maxLen; k++) {
if (max[k] == 0) {
max[k] = c[j];
maxIndex[k] = j;
break; // 在后面加一个就要退出循环了
}
}
}
}
}
for (j = 0; j < maxLen; j++) {
if (max[j] > 0) {
System.out.println("第" + (j + 1) + "个公共子串:");
for (i = maxIndex[j] - max[j] + 1; i <= maxIndex[j]; i++)
System.out.print(str1[i]);
System.out.println(" ");
}
}
}
public static void main(String[] args) {
String str1 = new String("123456abcd567");
String str2 = new String("234dddabc45678");
// String str1 = new String("aab12345678cde");
// String str2 = new String("ab1234yb1234567");
getLCString(str1.toCharArray(), str2.toCharArray());
}
}
ref：
LCS的java算法---考虑可能有多个相同的最长公共子串
http://blog.csdn.net/rabbitbug/article/details/1740557
最大子序列、最长递增子序列、最长公共子串、最长公共子序列、字符串编辑距离
http://www.cnblogs.com/zhangchaoyang/articles/2012070.html
2.2 其实 awk 写起来也很容易：
echo "123456abcd567
234dddabc45678"|awk -vFS="" ‘NR==1{str=$0}NR==2{N=NF;for(n=0;n++<N;){s="";for(t=n;t<=N;t++){s=s""$t;if(index(str,s)){a[n]=t-n;b[n]=s;if(m<=a[n])m=a[n]}else{t=N}}}}END{for(n=0;n++<N;)if(a[n]==m)print b[n]}‘
ref：http://bbs.chinaunix.net/thread-4055834-2-1.html
2.3 perl的。。。真心没看懂。。。
#!/usr/bin/perl
use strict;
use warnings;
my $str1 ="123456abcd567";
my $str2 = "234dddabc45678";
my $str = $str1 . "\n" . $str2;
my (@substr,@result);
$str =~ /(.+)(?=.*\n.*\1)(*PRUNE)(?{push @substr,$1})(*F)/;
@substr = sort { length($b) <=> length($a) } @substr;
@result = grep { length == length $substr[0] } @substr;
print "@result\n";
ref： http://bbs.chinaunix.net/thread-1333575-7-1.html
3、最长公共子序列
import java.util.Random;
public class LCS {
public static void main(String[] args) {
// 随机生成字符串
// String x = GetRandomStrings(substringLength1);
// String y = GetRandomStrings(substringLength2);
String x = "a1b2c3";
String y = "1a1wbz2c123a1b2c123";
// 设置字符串长度
int substringLength1 = x.length();
int substringLength2 = y.length(); // 具体大小可自行设置
// 构造二维数组记录子问题x[i]和y[i]的LCS的长度
int[][] opt = new int[substringLength1 + 1][substringLength2 + 1];
// 从后向前，动态规划计算所有子问题。也可从前到后。
for (int i = substringLength1 - 1; i >= 0; i--) {
for (int j = substringLength2 - 1; j >= 0; j--) {
if (x.charAt(i) == y.charAt(j))
opt[i][j] = opt[i + 1][j + 1] + 1;// 状态转移方程
else
opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);// 状态转移方程
}
}
System.out.println("substring1:" + x);
System.out.println("substring2:" + y);
System.out.print("LCS:");
int i = 0, j = 0;
while (i < substringLength1 && j < substringLength2) {
if (x.charAt(i) == y.charAt(j)) {
System.out.print(x.charAt(i));
i++;
j++;
} else if (opt[i + 1][j] >= opt[i][j + 1])
i++;
else
j++;
}
}
// 取得定长随机字符串
public static String GetRandomStrings(int length) {
StringBuffer buffer = new StringBuffer("abcdefghijklmnopqrstuvwxyz");
StringBuffer sb = new StringBuffer();
Random r = new Random();
int range = buffer.length();
for (int i = 0; i < length; i++) {
sb.append(buffer.charAt(r.nextInt(range)));
}
return sb.toString();
}
}
REF：
字符串最大公共子序列以及最大公共子串问题
http://gongqi.iteye.com/blog/1517447
动态规划算法解最长公共子序列LCS问题
http://blog.csdn.net/v_JULY_v/article/details/6110269
原文：http://my.oschina.net/airship/blog/411107
内容总结
以上是互联网集市为您收集整理的动态规划算法之：最长公共子序列 & 最长公共子串（LCS）全部内容，希望文章能够帮你解决动态规划算法之：最长公共子序列 & 最长公共子串（LCS）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。