每日OJ_牛客HJ65 查找两个字符串a,b中的最长公共子串

目录

HJ65 查找两个字符串a,b中的最长公共子串

解析代码

HJ65 查找两个字符串a,b中的最长公共子串

查找两个字符串a,b中的最长公共子串_牛客题霸_牛客网

解析代码

        本题是一道动态规划dp题，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)即为所求。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
string getComSubstr(string& str1, string& str2) // 寻求最短字符串
{
    if (str1.size() > str2.size())
        swap(str1, str2);
 
    int len1 = str1.size();
    int len2 = str2.size();
    vector<vector<int>> MSC(len1 + 1, vector<int>(len2 + 1, 0));
    int start = 0, max_size = 0;
    for (int i = 1; i <= len1; ++i)
    {
        for (int j = 1; j <= len2; ++j)
        {
            if (str2[j - 1] == str1[i - 1])
                MSC[i][j] = MSC[i - 1][j - 1] + 1;
            if (MSC[i][j] > max_size)
            {
                max_size = MSC[i][j];
                start = i - max_size;
            }
        }
    }
    return str1.substr(start, max_size);
}
 
int main()
{
    string str1, str2;
    while (cin >> str1 >> str2)
    {
        string substr = getComSubstr(str1, str2);
        cout << substr << endl;
    }
    return 0;
}