79. 最长公共子串

描述

给出两个字符串，找到最长公共子串，并返回其长度。
子串的字符应该连续的出现在原字符串中，这与子序列有所不同。

样例

给出A=“ABCD”，B=“CBCE”，返回 2

挑战

O(n x m) time and memory.

思路
比较简单，

代码

1. 暴力解法，枚举出所有的子串，i 和 j 代表子串的起点，current 代表子串的长度， i + current 和 j + current 代表子串的终点

public int longestCommonSubstring(String A, String B) {
    int n = A.length();
    int m = B.length();
    int max = 0;
        
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // current 代表当前子串长度
            int current = 0;
            // while 循环的时间复杂度为 O(n)
            while (i + current < n && j + current < m && A.charAt(i + current) == B.charAt(j + current))
                current++;
            max = Math.max(max, current);
        }
    }
    return max;
}

2. dp 但并不是最优

public class Solution {
    /**
     * @param A, B: Two string.
     * @return: the length of the longest common substring.
     */
    public int longestCommonSubstring(String A, String B) {
        // f[i][j] 代表以当前 i - 1 和 j -1 为终点的两个子串中同样以以 i 和 j 为终点的最长公共子串长度
        // 注意 f[i][j] 描述的最长公共子串的终点也是 i - 1 和 j - 1
        int n = A.length();
        int m = B.length();
        int[][] f = new int[n + 1][m + 1];
        
        // initialize: f[i][j] is 0 by default
        
        // function: f[i][j] = f[i - 1][j - 1] + 1 or 0
        // i 和 j 分别代表子串的终点
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (A.charAt(i) == B.charAt(j)) {
                    f[i+1][j+1] = f[i][j] + 1;
                // 如果终点不相等，以 i j 为终点的公共子串的长度也就变成了 0
                } else {
                    f[i+1][j+1] = 0;
                }
            }
        }
        
        // answer: max{f[i][j]}
        int max = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                max = Math.max(max, f[i][j]);
            }
        }
        
        return max;
    }
}