Longest Common Substring

Med Given two strings, find the longest common substring.

Return the length of it.

Thoughts

f[i][j]表示第i个字符和第j个字符作为lcs的尾时最长长度。不难，但思路相比前两道题需要稍微转换下。

Code

public class Solution {
    /**
     * @param A, B: Two string.
     * @return: the length of the longest common substring.
     */
    public int longestCommonSubstring(String A, String B) {
        int m = A.length();
        int n = B.length();

        if (m == 0 || n == 0) {
            return 0;
        }

        // f: 以A[i], B[j]为尾的最长序列长度
        int[][] f = new int[m + 1][n + 1];

        // loop
        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;
                }
            }
        }

        // end
        int res = Integer.MIN_VALUE;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                res = Math.max(res, f[i][j]);
            }
        }

        return res;
    }
}

Analysis

TC: O(mn)