最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。求解使用费曼算法（Feynman algorithm）

费曼算法

步骤：

1. 将问题写下来
2. 好好思考
3. 将答案写下来
   佩服呀，真是万能算法 。。。org

最长公共子串

先了解一下最长公共子串，例子str1=“abcdefg” ，str2=“bcdgh” 最长公共子串为bcd。

填充网格

求fish 与 hish 的最长子串长度为3

用网格描述如下：

算法解释

核心代码

注意

最长公共子串长度为二维数组中最大的那个值

最长公共子序列

fort 与 fosh最长公共子序列长度为2，fish 与 fosh 最长公共子序列长度为 3

网格描述如下：

算法解释

核心代码

源码

public class LCS2 {

	public static void main(String[] args) {
		String a="123456";
		String b="2468";
		char c[]=new char[a.length()+1];
		char d[]=new char[b.length()+1];
		for(int i=1;i<=a.length();i++)
			c[i]=a.charAt(i-1);
		for(int i=1;i<=b.length();i++)
			d[i]=b.charAt(i-1);
		int map[][]=new int[a.length()+1][b.length()+1];//横竖都空一行
		for(int i=1;i<=a.length();i++) {
			for(int j=1;j<=b.length();j++) {
				if(c[i]==d[j]) {
					map[i][j]=map[i-1][j-1]+1;
				}
				else {
					map[i][j]=Math.max(map[i-1][j], map[i][j-1]);
				}
			}
		}
		System.out.println(map[a.length()][b.length()]);

	}

}

参考书籍

《算法图解》