递归和动态规划——最长公共子串

题目：给定两个字符串，返回两个字符串的最长公共子串。
例：
str1=”1AB2345CD”，str3=”12345EF”，返回”2345”。
str1=”abcde”，str2=”bebcd“。最长公共子串为”bcd”。
要求：若str1和str2的长度分别为M和N，要求时间复杂度为O(M*N)，额外的空间复杂度为O(1)。

实现：（注意公共子串在原字符串中连续，注意这与上一节的求解两个字符串的公共子序列不同：递归和动态规划——最长公共子序列不同）。
方法一(经典方法)：时间复杂度为O(M*N)，额外的空间复杂度为O(M*N)。
生成大小为M*N的动态规划表dp，dp[i][j]表示把str1[i]和str[j]当做公共子串最后一个字符的情况下，最长公共子串能有多长。
1.dp的第一列dp[0,..M-1][0],如果str1[i]== str2[0]，则dp[i][0]=1，否则dp[i][0]=0。
2.dp的第一行dp[0][0,..N-1]，原理与第一列相同，如果str1[0]== str2[j]，则dp[0][j]=1，否则dp[0][j]=0。
3.对于非第一行和第一列，有以下两种可能情况：
1）若str1[i]!=str2[j]，说明把str1[i]和str2[j]当做公共子串的最后一个字符串是不可能的，所以dp[i][j]=0；
2）若str1[i]==str2[j]，说明str1[i]和str2[j]可以作为公共子串的最后一个字符串。从最后一个字符串能向左扩展多长呢，就是dp[i-1][j-1]的值，即令dp[i][j]=dp[i-1][j-1]+1。

dp表	b	e	b	c	d
a	0	0	0	0	0
b	1	0	1	0	0
c	0	0	0	2	0
d	0	0	0	0	3
e	0	1	0	0	0
4.根据动态规划表生成最长公共子串。
1）先找dp中数值最大的dp[i][j]，它就是最长公共子串的长度len。将值i(或j作为str2）作为str1的最后一个索引end。
2）根据str1.substring(end-len+1,end+1)。注意substring的beginIndex和endIndex的取值，endIndex是子串的下一个索引，如str=”abcd”，str.substring(1,3)的结果为”bc”。

方法二：
经典动态规划算法的dp矩阵是M*N维的，但注意到计算每一个dp[i][j]的时候，只使用了其左上方的dp[i-1][j-1]的值，所以按照斜线方向来计算所有的值，只需要一个变量就可以计算出所有位置的值。
1.每一条斜线在计算之前定义整型变量len，表示左上方的值，初始化为len=0。从左上方到右下方依次计算每个位置的值。
2.对于位置(i, j)，此时len表示位置(i-1,j-1)的值。
1）如果str1==str2，那么位置(i,j)的值为len+1；
2）如果str1!=str2，那么位置(i,j)的值为0。
3.依次计算得到斜线上每个位置的值，然后计算下一条斜线。

用一个全局变量max记录所有位置中的最大值，相应的位置用全局变量end记录。

public class LongComSubseq {
	/**
	 * 方法一：利用M*N的动态规划表，时间和空间复杂度为O(M*N)
	 * 1. 生成动态规划表dp，dp[i][j]表示
	 * 把str[i]和str2[j]作为公共子串的最后一个字符时， 公共子串最长能有多长
	 * @param str1 str1对应的字符串数组
	 * @param str2 str2对应的字符串数组
	 * @return 动态规划表dp
	 */
	public int[][] getDp(char[] str1, char[] str2) {
		int[][] dp = new int[str1.length][str2.length];
		//第一列
		for (int i = 0; i < str1.length; i++) {
			if (str1[i] == str2[0]) {
				dp[i][0] = 1;
			} //默认其它项都为0
		}
		for (int j = 1; j < str2.length; j++) {
			if (str1[0] == str2[j]) {
				dp[0][j] = 1;
			}
		}
		for (int i = 1; i < str1.length; i++) {
			for (int j = 1; j < str2.length; j++) {
				if(str1[i] == str2[j]) {
					dp[i][j] = dp[i-1][j-1] + 1;
				}
			}
		}
		return dp;
	}
	/**
	 * 2. 根据动态规划表生成最长公共子串
	 * @param str1 需要进行比较的字符串str1
	 * @param str2 需要进行比较的字符串str2
	 * @return 最长公共子串
	 */
	public String longComSubseq (String str1, String str2) {
		if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) {
			return ""; //返回空字符串
		}
		char[] cha1 = str1.toCharArray();
		char[] cha2 = str2.toCharArray();
		int[][] dp = getDp(cha1, cha2);
		int len = 0;
		int end = 0;
		for (int i = 0; i < cha1.length; i++) {
			for (int j = 0; j < cha2.length; j++) {	
				if (dp[i][j] > len) { //找dp矩阵中的最大值
					len = dp[i][j];
					end = i;
				}
			}
		}
		return str1.substring(end - len + 1, end + 1);
		//注意substring的beginIndex和endIndex的取值，endIndex是子串的下一个索引
		//如str="abcd"，str.substring(1,3)为"bc"。
	}

/**
 * 方法二：不需要建立dp动态规划表，时间复杂度为O(M*N)，空间复杂度为O(1)
 * 只需要两个全局变量记录以某个字符结尾的最大长度max，和最大长度更新的子串的结尾位置
 * @param str1
 * @param str2
 * @return
 */
public String longComSubseq2(String str1, String str2) {
	if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) {
		return "";
	}
	char[] cha1 = str1.toCharArray();
	char[] cha2 = str2.toCharArray();
	//斜线开始的位置为右上角，而每一条斜线是从左上角到右下角，走完每一条斜线到达左下角。
	int row = 0; //斜线开始位置的行
	int col = cha2.length - 1; //斜线开始位置的列
	int max = 0; //记录最大长度
	int end = 0; //最大长度更新时的子串的结尾位置
	//一行一行地从左上到右下遍历
	while (row < cha1.length) {
		int i = row;
		int j = col;
		int len = 0; //表示斜线左上方的值
		//从(i,j)开始向右下方遍历
		while (i < cha1.length && j < cha2.length) {
			if (cha1[i] != cha2[j]) {
				len = 0;
			} else {
				len++;
			}
			if (len > max) {
				max = len;
				end = i;
			}
			i++;
			j++;
		}
		if (col > 0) { //斜线开始向左移动
			col--;
		} else { //到了最左边后开始向下移动
			row++;
		}
	}
	return str1.substring(end - max + 1, end + 1);
}

	//Test
	public static void main(String[] args) {
		LongComSubseq lcs = new LongComSubseq();
		String str1 = "abcde";
		String str2 = "ebcd";
	    System.out.println("str1和str2的动态规划表为;");
		char[] cha1 = str1.toCharArray();
		char[] cha2 = str2.toCharArray();
		int[][] dp = lcs.getDp(cha1,cha2);
		for (int[] i : dp) {
			 for (int j : i) {
				 System.out.print(j + " ");
			 }
			 System.out.println();
		}
		System.out.println("方法一得到的最长公共子串为：" + lcs.longComSubseq(str1, str2));
		System.out.println("方法二得到的最长公共子串为：" + lcs.longComSubseq2(str1, str2));
	}
}

输出：

str1和str2的动态规划表为;
0 0 0 0 
0 1 0 0 
0 0 2 0 
0 0 0 3 
1 0 0 0 
方法一得到的最长公共子串为：bcd
方法二得到的最长公共子串为：bcd