Longest Common Substring.java

M
1525239157
tags: DP, Double Sequence DP, String, Sequence DP

#### Double Sequence DP
- 两个string, 找最值: longest common string length
- 序列型, 并且是双序列, 找两个序列 (两维的某种性质)
- dp[i][j]: 对于 A 的前i个字母, 对于 B 的前j个字母, 找最长公共substring的长度
- dp = new int[m + 1][n + 1]
- dp[i][j] = dp[i - 1][j - 1] + 1; only if A.charAt(i - 1) == B.charAt(j - 1)
- 注意track max, 最后return
- space O(n^2), time(n^2)

##### Rolling array
- 空间优化, [i] 只有和 [i - 1] 相关, 空间优化成 O(n)

#### String
- 找所有A的substring, 然后B.contains()
- track max substring length
- O(n^2) time

```
/*
Given two strings, find the longest common substring.

Return the length of it.

Example
Given A = "ABCD", B = "CBCE", return 2.

Note
The characters in substring should occur continuously in original string. This is different with subsequence.

Challenge
O(n x m) time and memory.

Tags Expand 
LintCode Copyright Longest Common Subsequence Dynamic Programming

*/

/**
Thoughts: double sequence DP
dp[i][j]: for first i chars in A, and first j chars in B, what's the longest common substring length?

init:
if i == 0 || j == 0, no common substring, dp[i][j] = 0;

function:
dp[i][j] = dp[i - 1][j - 1] + 1; only if A.charAt(i - 1) == B.charAt(j - 1)
otherwise, dp[i][j] = 0; start over

Track max
*/
public class Solution {
    public int longestCommonSubstring(String A, String B) {
    	if (A == null || B == null || A.length() == 0 || B.length() == 0) {
    		return 0;
    	}
    	int m = A.length();
    	int n = B.length();
    	int[][] dp = new int[m + 1][n + 1];
    	int max = 0;
    	for (int i = 0; i <= m; i++) {
    		for(int j = 0; j <= n; j++) {
    		    if (i == 0 || j == 0) {
    		        dp[i][j] = 0;
    		        continue;
    		    }
    			if (A.charAt(i - 1) == B.charAt(j - 1)) {
    				dp[i][j] = dp[i - 1][j - 1] + 1;
    			} else {
    				dp[i][j] = 0;
    			}
        		max = Math.max(max, dp[i][j]);
    		}
    	}
    	return max;
    }
}

// Rolling array, space O(n)
public class Solution {
    public int longestCommonSubstring(String A, String B) {
    	if (A == null || B == null || A.length() == 0 || B.length() == 0) {
    		return 0;
    	}
    	int m = A.length();
    	int n = B.length();
    	int[][] dp = new int[2][n + 1];
    	int max = 0;
    	for (int i = 0; i <= m; i++) {
    		for(int j = 0; j <= n; j++) {
    		    if (i == 0 || j == 0) {
    		        dp[i % 2][j] = 0;
    		        continue;
    		    }
    			if (A.charAt(i - 1) == B.charAt(j - 1)) {
    				dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1;
    			} else {
    				dp[i % 2][j] = 0;
    			}
        		max = Math.max(max, dp[i % 2][j]);
    		}
    	}
    	return max;
    }
}





/**
String: find all possible substring, try all of them
O(n^2)
 */
public class Solution {
    public int longestCommonSubstring(String A, String B) {
    	if (A == null || B == null || A.length() == 0 || B.length() == 0) {
    		return 0;
    	}
    	int n = A.length();
    	
    	int max = 0;
    	for (int i = 0; i < n; i++) {
    		for(int j = 0; j <= i; j++) {
    		    String subStr = A.substring(j, i + 1);
        		if (B.contains(subStr)) {
        		    max = Math.max(max, subStr.length());
        		}
    		}
    	}
    	return max;
    }
}

/**
Previous notes
Thoughts:
1. Compare all i X j.
2. Use a D[i][j] to mark the amount of common substring based on D[i - 1][j -1]. Could be 0.
3. track max length

NOTE1: create 2D array that's [N + 1][M + 1] because we want to hold D[n][M] in the 2d array
NOTE2: be carefule with init index 0's
 */
public class Solution {
    /**
     * @param A, B: Two string.
     * @return: the length of the longest common substring.
     */
    public int longestCommonSubstring(String A, String B) {
    	if (A == null || B == null || A.length() == 0 || B.length() == 0) {
    		return 0;
    	}   
    	int [][] D = new int[A.length() + 1][B.length() + 1];
    	int max = 0;
    	for (int i = 0; i <= A.length(); i++) {
    		for(int j = 0; j <= B.length(); j++) {
    		    if (i == 0 || j == 0) {
    		        D[i][j] = 0;
    		    } else {
        			if (A.charAt(i - 1) == B.charAt(j - 1)) {
        				D[i][j] = D[i - 1][j - 1] + 1;
        			} else {
        				D[i][j] = 0;
        			}
        			max = Math.max(max, D[i][j]);
    		    }
    		}
    	}
    	return max;
    }
}



```