文档章节

动态规划算法之:最长公共子序列 & 最长公共子串(LCS)

大数据之路
 大数据之路
发布于 2013/03/25 01:30
字数 1182
阅读 53391
收藏 27

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


本文转载自:

大数据之路
粉丝 1605
博文 514
码字总数 333043
作品 0
武汉
架构师
私信 提问
加载中

评论(2)

siri李
siri李

引用来自“沉默喝豆浆”的评论

你好博主,我对求最长公共子串的java代码(第一个代码)有些疑惑,24行,为什么如果是大于那暂时只有一个是最长的,就要把后面的清0呢?烦请帮我解答一下,谢谢!
应该是为了解决多个最长公共字串相等的问题,但是感觉写的有点儿别扭
沉默喝豆浆
沉默喝豆浆
你好博主,我对求最长公共子串的java代码(第一个代码)有些疑惑,24行,为什么如果是大于那暂时只有一个是最长的,就要把后面的清0呢?烦请帮我解答一下,谢谢!
有趣的算法问题之巧思妙想

有趣的算法 算法之所以有趣,在于他能够化繁为简,他能概括统御世间万物,将一个复杂的问题归结为一个非常简单的问题。其实所有高阶的算法,都可以用两个大的方法去解决,而且屡试不爽。分别...

Nicholas_Jela
2017/09/06
0
0
算法与数据结构(二):动态规划(DP)总结

版权声明:版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/Dbyfreedom https://blog.csdn.net/Dbyfreedom/article/details/89388883 1. 最长公共子序列 题目描...

dby_freedom
04/21
0
0
Leetcode【712、746、877】

问题描述:【DP】712. Minimum ASCII Delete Sum for Two Strings 解题思路: 读完题目后发现:把两个字符串中多余的字符删除后,最后留下的字符串是两个字符串的最长公共子序列。因此这道题...

牛奶芝麻
06/09
0
0
删除部分字符使其变成回文串问题——最长公共子序列LCS问题

先要搞明白:最长公共子串和最长公共子序列的区别。 最长公共子串(Longest Common Substirng):连续 最长公共子序列(Longest Common Subsequence,LCS):不必连续 题目:给定一个字符串s...

牧师-Panda
2016/09/10
702
0
动态规划

动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长非降子序列(LIS) 最大乘积子串 Unique Paths Unique Paths II Minimum Path Sum Triangle 最...

廖少少
2017/09/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

for循环

九九乘法表 示例:for(int i = 1; i <= 9; i++){ for (int j = 1; j <= i; j++) { // 每次开始i循环,j都会重新定义为j=1,然后开始循环计算 System.out.print(j +......

Shutting
21分钟前
7
0
小王子1

一定要帅! 韩国设计师品牌 insgram全世界得网红 韩国潮男穿搭 HM 找到穿衣服最好看的人,跟他比,比他好看。 在兴趣前,不要表现目的性,压力 关系是不热就冷的! 不喜欢压力,不喜欢负责任...

阿锋zxf
40分钟前
10
0
时间戳

1 loadTimeString(ts) { var d = new Date(); if (String(ts).length == 10) { d = new Date(ts * 1000); ......

东方巨人
42分钟前
7
0
Redis Cluster

Redis Cluster 集群 redis集群有以下几种方式 普通一主多从 普通一主多从+哨兵 cluster分片模式 一主多从 搭建方式网上很多,就不多描述了。 这种集群方式,一般master用作写,slave用做读,...

lazy~
42分钟前
13
0
 介绍一款优秀的通用管理权限快速开发框架

这是一套以权限管理为主的轻量化快速开发框架,配置有流程、专业表单、权限、app、企业微信等基础功能模块,在开发通用软件的效率上很有优势。 软件平台常用研发需求分析 《那些年我们一起做...

我想造火箭
58分钟前
16
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部