Longest Common Substring

Given two strings, find the longest common substring.

Return the length of it.

Notes:

1. Double sequence DP
2. State: f[i][j] the common substring at A[i] and B[j]
3. Function: f[i][j] = f[i-1][j-1] + 1 when A[i-1] == B[j-1], get the max of f[i][j]
4. Initialize: 0
5. Answer: max

    public int longestCommonSubstring(String A, String B) {
        if (A == null || B == null || A.isEmpty() || B.isEmpty()) {
            return 0;
        }

        // state
        int m = A.length();
        int n = B.length();
        int[][] f = new int[m+1][n+1];

        // initialize
        // 0, skip

        // function
        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)) {
                    f[i][j] = f[i-1][j-1]+1;
                    max = Math.max(max, f[i][j]);
                }
            }
        }

        // answer
        return max;
    }