Longest Common Substring

Longest Common Substring

Description:

Given two strings, find the longest common substring. Return the length of it.

Notice:

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

Example:

Given A = “ABCD”, B = “CBCE”, return 2.

分析：

动态规划。

  1. 最优子结构。

  2. 重叠子问题。

因为只涉及两个 word 之间的状态转换，所以是个二维dp，关键是如何得到递推关系。

可以假设dp[i][j] = m表示A[i]和B[j]的后m个子串（不是子序列）相等。分两种情况讨论：

  1. A[i] == B[j]。注意要求是字串，要求连续，当i > 0 && j > 0时，还需要看A[i-1] == B[j-1]是否成立（这一个当时忘记写了，string a = “aaaaaaaaaaaabbbbbcdd”; string b = “abcdd”;没通过）。

    • 如果成立，说明各自前面的一个字符也相等，则有：dp[i+1][j+1] = max(max(dp[i][j]+1, dp[i][j+1]), dp[i+1][j]);。

    • 否则，说明这是本次第一个相等的字符：dp[i+1][j+1] = 1;。（这一个当时忘记写了，string a = “www.lintcode.com code”; string b = “abcdd”;没通过）

  2. A[i] != B[j]，此时dp[i][j] = 0。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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
        vector<vector<int> > dp(A.size()+1, vector<int>(B.size()+1, 0));
        int rs = 0;
        
        for (int i = 0; i < A.size(); i++) {
            for (int j = 0; j < B.size(); j++) {
                if (A[i] == B[j]) {
                    if (i > 0 && j > 0) {
                        if (A[i-1] == B[j-1]) {
                            dp[i+1][j+1] = max(max(dp[i][j]+1, dp[i][j+1]), dp[i+1][j]);
                        }
                        else {
                            dp[i+1][j+1] = 1;
                        }
                    }
                    else {
                        dp[i+1][j+1] = max(max(dp[i][j]+1, dp[i][j+1]), dp[i+1][j]);
                    }
                }
                // else {
                //     dp[i+1][j+1] = max(max(dp[i][j], dp[i][j+1]), dp[i+1][j]);
                // }
                
                rs = max(rs, dp[i+1][j+1]);
            }
        }
        return rs;
    }
};