Longest Common Substring

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.

Solution: Dynamic Programming

public int longestCommonSubstring(String A, String B) {
    int[][] lcs = new int[A.length()][B.length()];
    int max = 0;
    for (int i = 0; i < A.length(); i++) {
        for (int j = 0; j < B.length(); j++) {
            if (A.charAt(i) == B.charAt(j)) {
                if (i == 0 || j == 0) {
                    lcs[i][j] = 1;
                } else {
                    lcs[i][j] = lcs[i - 1][j - 1] + 1;
                }
            }
            if (lcs[i][j] > max) {
                max = lcs[i][j];
            }
        }
    }
    return max;
}
FacebookTwitterGoogle+Share

Leave a Reply

Your email address will not be published. Required fields are marked *