Simpsons’ Hidden Talents（前缀后缀匹配plus

题目描述：

题意：

给定两个字符串，求a串中即是b串后缀又是本身前缀的最长串，如果没有就输出０

思路：

显然的nxt数组定义题，可以考虑讲两个字符串拼接起来然后nxt[a串长度+b串长度]（拼接起来后a串的前缀一定是b串的前缀b串的后缀一定是a串的后缀 ）,但是这样就会出现nxt[a串长度+b串长度]大于a或者b的长度，那么只需要往前找即可：while (nxt[j]>lena||nxt[j]>lenb)j=nxt[j]

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define end '\n'
#define IOS ios::sync_with_stdio(0)
int nxt[N],len=0;
void get_next(string p) {
    int j = 0, k = -1;
    nxt[0] = -1;
    while (j < len)
        if (k == -1 || p[j] == p[k])
            nxt[++j] = ++k;
        else
            k = nxt[k];
}
int main() {
    string a,b;
    IOS;
    while (cin>>a>>b){
        int lena=a.size(),lenb=b.size();
        a=a+b;
        len=lena+lenb;
        get_next(a);
        int j=len;
        while (nxt[j]>lena||nxt[j]>lenb)j=nxt[j];
        for(int i=0;i<nxt[j];i++)cout<<a[i];
        if (nxt[j]>0)cout<<" "<<nxt[j]<<end;
        else cout<<"0"<<end;
    }
    return 0;
}