最长公共子串（Longest Common Substring）

题目描述

给定两个序列X=(X1,X2,…,Xm)和Y=(Y1,Y2,…,Yn)，求X和Y的最长公共子串。
例如：输入两个字符串acbac和acaccbabb，则最大连续子串为cba, 则返回长度3。

解法一

参考之前关于最长公共子序列LCS的解法，我们发现LCS是一种通用的公共子序列，而子串是一种连续的子序列，所以需要修改递推公式。此处动态规划表格存放的内容有所不同，LCS是比较子串，当前问题是为了使用连续子串这一条件，所以考虑设数组dp[i,j]表示以Xi和Yj结尾的最大公共连续子串的长度，如果Xi=Yj，则dp[i,j]=dp[i-1,j-1]+1，只需要再考虑dp[i-1,j-1]这个子问题，如果不相等，则dp[i,j]=0，如果i=0或j=0，说明有一个字符串已经结束了，则dp[i,j]=0。需要注意的是，dp的含义决定了最后的输出结果不是dp[m,n]，而必须在计算dp的过程中寻找最大值。

递归+memo：

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
class Solution {
public:
    int longestCommonSubstring(string text1, string text2) {
        int size1 = text1.size();
        int size2 = text2.size();
        int memo[1001][1001];
        memset(memo, 0, 1001*1001*sizeof(int));
        int max_len = 0;
        int end_index;
        lcs(text1, text2, memo, size1-1, size2-1, max_len, end_index);
        cout<<text1.substr(end_index-max_len+1, max_len);
        return max_len;
    }

    int lcs(string & a, string & b, int memo[][1001], int i, int j, int & max_len, int & end_index) {
        if(i == -1 || j == -1) return 0; // 有一个字符串已经结束
        if(memo[i][j] != -1) return memo[i][j];
        if(a[i] == b[j]) {
            memo[i][j] = lcs(a, b, memo, i-1, j-1, max_len, end_index) + 1;
        } else {
            memo[i][j] = 0;
            // 此处这么做为了使lcs继续推进 不然遇到零就停下来了
            lcs(a, b, memo, i, j-1, max_len, end_index);
            lcs(a, b, memo, i-1, j, max_len, end_index);
        }
        if(memo[i][j] > max_len) {
            max_len = memo[i][j];
            end_index = i;
        }
        return memo[i][j];
    }
};

解法二

自底向上的解法

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
class Solution {
public:
    int longestCommonSubstring(string text1, string text2) {
        int dp[1001][1001];
        // memset更高效 memset针对cpu指令集做了优化
        memset(dp, 0, 1001*1001*sizeof(int));
        int size1 = text1.size();
        int size2 = text2.size();
        int max_len = 0;
        int end_index;
        // 从1开始 是为了把c[0,j]和c[i,0]留给空字符串用
        for(int i = 1; i <= size1; i++) {
            for(int j = 1; j <= size2; j++) {
                if(text1[i-1] == text2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = 0;
                }
                // 保存最大长度
                if(dp[i][j] > max_len) {
                    max_len = dp[i][j];
                    end_index = i-1;
                }
            }
        }
        cout<<text1.substr(end_index-max_len+1, max_len);
        return max_len;
    }
};