最长公共子串 Longest Common Subsequence

标签: 子串 longest common | 发表时间:2013-10-27 18:39 | 作者:hellobinfeng
出处:http://blog.csdn.net

动态规划的经典题!

package DP;

import java.util.Arrays;

// 最长公共子串 Longest Common Subsequence
public class LCS {

	static int dp[][] = null;
	
	public static void main(String[] args) {
		String a = "ABCABCBAASJKDFHSDDSJSAHJSD";
		String b = "CBABCABCCSDESJASDFHSDFSW";
		
		dp = new int[a.length()+1][b.length()+1];
		for(int[] row : dp){
			Arrays.fill(row, -1);
		}
		
		System.out.println(lcs2(a.toCharArray(), a.length(), b.toCharArray(), b.length()));
		System.out.println(lcs3(a.toCharArray(), a.length(), b.toCharArray(), b.length()));
//		print();
		System.out.println(lcs(a.toCharArray(), a.length(), b.toCharArray(), b.length()));
		
	}

	// 纯递归O(m*2^n)
	public static int lcs(char[] A, int m, char[] B, int n){
		if(m==0 || n==0){
			return 0;
		}
		
		if(A[m-1] == B[n-1]){
			return 1 + lcs(A, m-1, B, n-1);
		}else{
			return Math.max(lcs(A, m, B, n-1), lcs(A, m-1, B, n));
		}
	}
	
	// DP, top-down O(n^2)
	public static int lcs2(char[] A, int m, char[] B, int n){
		if(m==0 || n==0){
			return 0;
		}
		
		// 如果已经存在dp数组中,直接返回
		if(dp[m][n] != -1){
			return dp[m][n];
		}
		int res = 0;
		if(A[m-1] == B[n-1]){
			res = 1 + lcs2(A, m-1, B, n-1);
		}else{
			res = Math.max(lcs2(A, m, B, n-1), lcs2(A, m-1, B, n));
		}
		dp[m][n] = res;		// 把新值记录到dp数组中
		return res;
	}
	
	// DP, bottom-up O(n^2)
	public static int lcs3(char[] A, int m, char[] B, int n){
		for(int i=0; i<=m; i++){
			for(int j=0; j<=n; j++){
				if(i==0 || j==0){
					dp[i][j] = 0;
				}
				else if(A[i-1] == B[j-1]){
					dp[i][j] = dp[i-1][j-1] + 1;
				}
				else{
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
				}
			}
		}
		return dp[m][n];
	}
	
	public static void print(){
		for(int i=0; i<dp.length; i++){
			for(int j=0; j<dp[0].length; j++){
				System.out.print(dp[i][j] + " ");
			}
			System.out.println();
		}
	}
}





Ref:

http://www.csie.ntnu.edu.tw/~u91029/LongestCommonSubsequence.html

http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

http://techieme.in/techieme/dynamic-programming-longest-common-subsequence/

http://www.cc.gatech.edu/~ninamf/Algos11/lectures/lect0311.pdf

http://blog.gaurav.im/?p=9

http://blog.csdn.net/alexander_xfl/article/details/11556655

作者:hellobinfeng 发表于2013-10-27 10:39:12 原文链接
阅读:0 评论:0 查看评论

相关 [子串 longest common] 推荐:

最长公共子串 Longest Common Subsequence

- - CSDN博客推荐文章
package DP; import java.util.Arrays; // 最长公共子串 Longest Common Subsequence public class LCS {. // 纯递归O(m*2^n). // 如果已经存在dp数组中,直接返回. // 把新值记录到dp数组中. 作者:hellobinfeng 发表于2013-10-27 10:39:12 原文链接.

Geeks面试题: Longest Common Subsequence (LCS)

- - CSDN博客推荐文章
It is a classic computer science problem, the basis of  diff (a file comparison program that outputs the differences between two files), and has applications in bioinformatics..

《Practical Common Lisp 中文版》样章

- 夜深 - Chun Tian (binghe)
(注:我的译作《Practical Common Lisp 中文版》将由人民邮电出版社图灵公司出版,不过由于种种原因目前该书还在紧张的编辑之中,最后确定的出版时间为 10 月底之前. 由于拖得比较久,个人感到愧对读者,因此经过和出版社的协商,现公开其中的一章供读者预览. 内容直接来自未经编辑的原始译稿,因此本文和最后出版的内容将在细节上有所出入,还请读者见谅) 第五章 函数 (英文原版).

《实用 Common Lisp 编程》译者序

- yat - Chun Tian (binghe)
最近忙得脚打后脑勺,但博客还要持续更新,所以无奈之下只好把我给《实用 Common Lisp 编程》一书撰写的译者序重新发表在这里,以方便那些尚未读过该书的潜在读者们. 说实话,今天重读了一遍以后,我被我自己写的文字给深深打动了,因为我的写作能力很不稳定,一篇好文不是随时都可以写得出来的. 也许这就是会写字的人和职业写手的区别所在吧.

视频:2380瓣橙子串联为iphone充电

- zealken - 萝卜网
又被老外的想法给打败了,2380个,估计够我吃十年了. (您也可以在土豆网观看: http://www.tudou.com/programs/view/0H_pQqhsYTg/ ). 因为盗链严重,而我们服务器带宽有限,所以图片设置了防盗链,请见谅. 如果您的阅读器看不到图片,请订阅 http://feed.luobo8.com/ 即可显示图片.