复试上机准备之最长公共子串 | Patrick's Space

题目要求

求 2 个字符串的最长公共子串（输出时不包含空格）,字符串长度不超过 255。

输入：

What’re your namess?

My namess are your.

输出：

reyour

namess

分析

最长公共子串/序列，是动态规划中一个非常经典的题型。但我之前接触的是最长公共子序列，子序列不要求序列的元素是相邻的，而子串需要元素是相邻的。

暴力法

两个循环，把序列 B 的每个元素开始的子串和 A 的所有元素进行比较，找出所有子串，从而找出最长子串。

void get_sub_str(string a, string b) {
    int len_a = a.length();
    int len_b = b.length();

    int start = 0, max_len = 0;

    for (int i = 0; i < len_a; ++i) {
        for (int j = 0; j < len_b; ++j) {
            // 当找到相等的时候就顺着比下去，直到不相同
            // 这里重新使用了一个变量 k，就不用改 i、j 了
            if (a[i] == b[j]) {
                int k = 1;
                while (i + k < len_a && j + k < len_b && (a[i + k] == b[j + k])) {
                    ++k;
                }
                if (k > max_len) {
                    start = i;
                    max_len = k;
                }
            }
        }
    }

    for (int i = start; i < start + max_len; ++i) {
        cout << a[i];
    }
    cout << endl;
}

不过上面这种实现只能输出第一个最长的子串，如果要输出所有最长子串，就要把所有有可能成为最长子串的子串保存下来，输出的时候再进行判断，只输出长度是最长的那些子串。

动态规划-空间换时间

我们可以用 m * n 的矩阵来存放相等的信息，如果 arr[m][n] != 0 则表明 a[m] == b[n]，子串就是斜对角线这些元素都不为零的那些位置。因此只用找最长的斜线即可。

为了简化找对角线的过程，我们可以让该点的元素值是左上方元素值加一，这样凭借元素值就知道序列的长度有多少了。

// 使用动态规划-空间换时间的方法
void print_sub_str(string a, string b) {
    int arr[256][256] = {0};

    int max_len = 0;
    for (int i = 0; i < a.length(); ++i) {
        for (int j = 0; j < b.length(); ++j) {
            if (a[i] == b[j]) {
                // 根据斜上方的元素来赋值
                if (i > 0 && j > 0) {
                    arr[i][j] = arr[i - 1][j - 1] + 1;
                }
                else {
                    arr[i][j] = 1;
                }
                if (arr[i][j] > max_len) {
                    max_len = arr[i][j];
                }
            }
        }
    }

    // 找到最有长度最长的子串
    for (int i = 0; i < a.length(); ++i) {
        for (int j = 0; j < b.length(); ++j) {
            if (arr[i][j] == max_len) {
                // 要注意这里 substr 第二个参数是子串的长度！！！而非结束位置
                cout << b.substr(j - max_len + 1, max_len) << endl;
            }
        }
    }
}

总结

无论是暴力法还是动态规划法都是有一定的技巧的。暴力法主要是注意一下变量是怎么安排的；动态规划法则要搞清楚是如何用时间换空间，如何减轻输出的计算量。