Longest Common Substring

Given two strings, find the longest common substring.

Return the length of it.

Example

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

state: dp[i][j] 表示必须包括i字符和j字符的前i个字符配上前j个字符的LCS长度(前i个字符和前j个字符完全匹配)

function: dp[i][j] 1.如果charAt[i] = charAt[j]: dp[i][j] = dp[i-1][j-1]

                         2. 如果不等于 dp[i][j]= 0

initial: dp[i][0] dp[0][j] 为0

return max

要维护一个max 每次的出来的dp[i][j]和max比较 return最后最大的max

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) {
            return 0;
        }
        int m = A.length();
        int n = B.length();
        int[][] dp = new int[m+1][n+1];
        int max = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (A.charAt(i-1) != B.charAt(j-1)) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    
                }
                max = Math.max(dp[i][j], max);
            }
        }
        return max;
    }
}