Longest Common Substring

Problem

See here.

Notes

跟Longest Common Subsequence问题类似，不同之处在于状态转移方程的第二种情况：

$$function: f[i][j] = 0 // a[i-1] != b[j-1]$$,也就是说要重新赋0，因为substring要求连续性。

结果不是f[m][n]，而是所有状态中的最大值。

Solution

int longestCommonSubstring(string &A, string &B) {
        // write your code here
        int m = A.length();
        int n = B.length();
        vector<vector<int> > lcs(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]) {
                    lcs[i][j] = lcs[i-1][j-1] + 1;
                } else {
                    lcs[i][j] = 0;
                }
            }
        }
        int maxlen = 0;
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                if(lcs[i][j] > maxlen) {
                    maxlen = lcs[i][j];
                }
            }
        }
        return maxlen;
    }

Complexity $$O(n^2)$$， 空间复杂度也是

// Time:  O(m * n)
// Space: O(min(m, n))

class Solution {
public:
    /**
     * @param A, B: Two string.
     * @return: the length of the longest common substring.
     */
    int longestCommonSubstring(string &A, string &B) {
        if (A.length() < B.length()) {
            return longestCommonSubstring(B, A);
        }

        // table[i][j] means the longest length of common substring
        // of A which ends with A[i - 1] and B which ends with B[j - 1].
        vector<vector<int>> table(2, vector<int>(A.length() + 1, 0));
        int longest = 0;

        // if A[i - 1] != B[j - 1]:
        //     table[i][j] = 0
        // if A[i - 1] == B[j - 1]:
        //     table[i][j] = table[i - 1][j - 1] + 1
        for (int i = 1; i < A.length() + 1; ++i) {
            for (int j = 1; j < B.length() + 1; ++j) {
                if (A[i - 1] != B[j - 1]) {
                    table[i % 2][j] = 0;
                } else {
                    table[i % 2][j] = table[(i - 1) % 2][j - 1] + 1;
                    longest = max(longest, table[i % 2][j]);
                }
            }
        }

        return longest;
    }
};