Lintcode 79: Longest Common Substring

https://www.lintcode.com/problem/longest-common-substring/description

Given two strings, find the longest common substring.

Return the length of it.

Example

Example 1:
 Input:  "ABCD" and "CBCE"
 Output:  2
 
 Explanation:
 Longest common substring is "BC"


Example 2:
 Input: "ABCD" and "EACB"
 Output:  1
 
 Explanation: 
 Longest common substring is 'A' or 'C' or 'B'

Challenge

O(n x m) time and memory.

Notice

The characters in substring should occur continuously in original string. This is different with subsequence.

Notes:

A classic DP problem. The only place needing to pay attention is that: this question is for substring, not subsequence.

let dp[i][j] represents the longest common substring ending with A[i] and A[j], respectively.

Thus,

when A[i] == A[j], dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = 0;  (that is the different part to sequnce...)

See the code below:

class Solution {
public:
    /**
     * @param A: A string
     * @param B: A string
     * @return: the length of the longest common substring.
     */
    int longestCommonSubstring(string &A, string &B) {
        // write your code here
        int m = A.size(), n = B.size(), res = 0;
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        //dp[i][j]: the lcs ending with A[i] & A[j], respectively.
        for(int i=1; i<=m; ++i) {
            for(int j=1; j<=n; ++j) {
                if(A[i-1] == B[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    res = max(res, dp[i][j]);
                }
            //    else dp[i][j] = 0; //not necessary
            }
        }
        return res;
    }
};

We can further compress the space.

See the code below:

class Solution {
public:
    /**
     * @param A: A string
     * @param B: A string
     * @return: the length of the longest common substring.
     */
    int longestCommonSubstring(string &A, string &B) {
        // write your code here
        int m = A.size(), n = B.size(), res = 0;
        vector<int> dp(n+1, 0);
        //dp[i][j]: the lcs ending with A[i] & A[j], respectively.
        for(int i=1; i<=m; ++i) {
            for(int j=n; j>=1; --j) {
                if(A[i-1] == B[j-1]) {
                    dp[j] = dp[j-1] + 1;
                    res = max(res, dp[j]);
                }
                else dp[j] = 0;//must have
            }
        }
        return res;
    }
};