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

#include <iostream>
#include <vector>
#include <string>
using namespace std;
//对较短串两个for循环遍历所有的子串，每一个子串都用kmp算法判断一下是否再长串中出现。O(m+n)
//对于在长串中出现的子串，找其中的最长值。遍历子串时从前往后遍历，保证在长度出现相等时，保留的最长值是最先在子串中出现的
vector<int> toNext(const string & str){
    vector<int>next(str.size(),0);
    int j=0;
    for(int i=1;i<str.size();i++){
        while(j>0&&str[j]!=str[i]){
            j=next[j-1];
        }
        if(str[j]==str[i]){
            j++;
        }
        next[i]=j;
    }
    return next;
}
int KMP(const string& s,const string& str){
    vector<int>next=toNext(str);
    int j=0;//j遍历模板串，i遍历文本串
    for(int i=0;i<s.size();i++){
        while(j>0&&s[i]!=str[j]){
            j=next[j-1];
        }
        if(s[i]==str[j]){j++;}
        if(j==str.size()){return i-str.size()+1;}
    }
    return -1;

}
int main() {
    string s1, s2;
    cin >> s1 >> s2;
    string slong, sshort;
    string longest=" ";
    int pos = -1;
    slong = s1.size() > s2.size() ? s1 : s2;
    sshort = s1.size() < s2.size() ? s1 : s2;
    for (int i = 0 ; i < sshort.size(); i++) {
        for(int j=i;j<sshort.size();j++){
        string str = sshort.substr(i,j-i+1);
        pos = KMP(slong, str);
        if(pos<0){break;}
        else if (pos >=0&&str.size()>longest.size()) {
            longest=str;
        }
    }}
    cout<<longest<<endl;
}