[每日一题] 38. 查找两个字符串a,b中的最长公共子串(字符串、动态规划、LCS问题)

1. 题目来源

链接：查找两个字符串a,b中的最长公共子串
来源：牛客网

2. 题目说明

查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。

输入描述：

输入两个字符串

输出描述：

返回重复出现的字符

示例：

输入：
abcdefghijklmnop
abcsafjklmnopqrstuvw
输出
jklmnop

3. 题目解析

本题需要用动态规划求解，MCS[i][j]记录短字符串 s1 前 i 个字符和长字符串 s2 前 j 个字符的最长子串的长度，初始化所有值为 0。当 s1[i-1] = s2[j-1]时，MCS[i][j] = MCS[i - 1][j - 1] + 1，这里使用一个额外的值 start 来记录最长子串在短字符串 s1 中出现的起始位置，maxlen记录当前最长子串的长度，当MCS[i][j] > maxlen 时，maxlen = MCS[i][j]， 则start = i - maxlen ；当s1[i-1] != s2[j-1]时不需要任何操作，最后获取 substr(start, maxlen)即为所求。

substr补充：

#include<string>
#include<iostream>
using namespace std;
int main()
{
　　string s("12345asdf");
　　string a = s.substr(0,5);     //获得字符串s中从第0位开始的长度为5的字符串
　　cout << a << endl;
}

// 输出：12345
1
2
3
4
5
6
7
8
9
10
11

0）用途：一种构造string的方法
1）形式：s.substr(pos, n)
2）解释：返回一个string，包含s中从pos开始的n个字符的拷贝（pos的默认值是0，n的默认值是s.size() - pos，即不加参数会默认拷贝整个s）
3）补充：若pos的值超过了string的大小，则substr函数会抛出一个out_of_range异常；若pos+n的值超过了string的大小，则substr会调整n的值，只拷贝到string的末尾。

4. 代码展示

#include <bits/stdc++.h>

using namespace std;

int main() {
    string str1, str2;
    while (cin >> str1 >> str2) {
        // 以最短的字符串作为s1
        if (str1.size() > str2.size())
            swap(str1, str2);
        int len1 = str1.size(), len2 = str2.size();
        int i, j, start = 0, max = 0;
        
        vector<vector<int>> MCS(len1 + 1, vector<int>(len2 + 1, 0));
        for (i = 1; i <= len1; ++i)
            for (j = 1; j <= len2; ++j) {
                if (str1[i - 1] == str2[j - 1])
                    MCS[i][j] = MCS[i - 1][j - 1] + 1;
                // 如果有更长的公共子串，更新长度
                if (MCS[i][j] > max) {
                    max = MCS[i][j];
                    // 以i结尾的最大长度为max，则子串的起始位置为i - max
                    start = i - max;
                }
            }
        cout << str1.substr(start, max) << endl;
    }
    return 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