题解 | #查找两个字符串a,b中的最长公共子串# 哈希

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

int main() {
    string str1, str2;
    cin >> str1 >> str2;
    // 记录长str和短str
    string str = str1, strShort = str2;
    if (str1.size() < str2.size()) {
        str = str2;
        strShort = str1;
    }
    // 遍历长string，然后存hash map
    unordered_set<string> strSet;
    for (int i = 0; i < str.size(); i++) {
        for (int j = 1; j <= str.size(); j++) {
            strSet.insert(str.substr(i, j - i));
        }
    }
    string res;
    int maxLen = 0;
    // 遍历较短的string，记录最大的公共子串的位置
    for (int i = 0; i < strShort.size(); i++) {
        for (int j = 1; j <= strShort.size(); j++) {
            auto subStr = strShort.substr(i, j - i);
            if (strSet.count(subStr) && subStr.size() > maxLen) {
                res = subStr;
                maxLen = subStr.size();
            }
        }
    }
    cout << res << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")