Lintcode: Longest Common Substring

Given two strings, find the longest common substring.

Return the length of it.

Have you met this question in a real interview? 

Yes

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.

Tags Expand 

LintCode Copyright Longest Common Subsequence Dynamic Programming

Way 1: three loops
reference: http://www.jiuzhang.com/solutions/longest-common-substring/

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: /** * @param A, B: Two string. * @return: the length of the longest common substring. */ int longestCommonSubstring(string &A, string &B) { // write your code here int Max = 0; //try all possible common substring for(int i = 0; i < A.size(); i++){ for(int j = 0; j < B.size(); j++){ int len = 0; while(i + len < A.size() && j + len < B.size()){ if(A[i + len] == B[j + len]) Max = max(Max, ++len); else break; } } } return Max; } };

Way 2: DP

http://www.cnblogs.com/yuzhangcmu/p/4199531.html

state s[i][j]: 表示包含B[j]以及之前连续字符的与A[i]及之前连续字符的共有的字符串长度

所以如果A[i], B[j]不等， s[i][j]为0；若相等，至少为1

function: if( A[i] = B[j])  s[i][j] = s[i - 1][j - 1] + 1;

                else s[i][j] = 0;

initialize: s[0][0] = 0;

answer: largest s[][]

Time complexity: O(mn)

Space complexity: O(mn)

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

TIP: there is a 1 dimension version, logic is same. 

Time: O(mn)       Space: O(n)

http://blog.csdn.net/nicaishibiantai/article/details/43448543

Just use the same array to rows of s[i][j]. To avoid rewriting, the second loop runs from back to front of B.