题解 | #公共子串计算#时空复杂度n^2/n^2解法

#include <unordered_map>
#include <iostream>
using namespace std;
/*
时间复杂度：n^2;
空间复杂度：n;
*/
int main() {
    int result = 0;
    string s,l;
    cin>>s>>l;
    int length_s = s.length();
    int length_l = l.length();
    //key为子串、int为长度
    unordered_map<string,int> s_map;
    unordered_map<string,int> l_map;
    //直接以子串作为key插入到unordered_map中，子串长度从1到length，进行遍历。
    for(int i=1;i<=length_s;i++){
        for(int j=0;j<length_s-i+1;j++){
            string temp = s.substr(j,i);
            if(s_map.find(temp)==s_map.end()) s_map.insert(make_pair(temp,temp.length()));
        }
    }
    for(int i=1;i<=length_l;i++){
        for(int j=0;j<length_l-i+1;j++){
            string temp = l.substr(j,i);
            if(l_map.find(temp)==l_map.end()) l_map.insert(make_pair(temp,temp.length()));
        }
    }
    unordered_map<string,int>::iterator itm;
    //找到键值相同的子串，并求最大值
    for(itm = s_map.begin();itm!=s_map.end();itm++){
        if(l_map.find(itm->first)!=l_map.end()&&itm->second>result){
        result = itm->second;
        }
    }
    cout<<result;
    return 0;
}