题解 | #字符串的问题#

思路

首先如果要求最大前缀的话，我们用Kmp就能线性求出来。
题目要求中间也有一个和最大前缀一样的东西，久相对增加了点难度。
那我们失配数组每个值出现的次数，如果最终nxt[len]（即整个串的最长后缀）出现过不止一次，
就可以输出答案了。但是这样写还需要考虑点细节。比如aaaa的情况，在中间出现的并不能达到最大后缀，该怎么处理？
我们考虑一下kmp的失配数组是啥东西。在当前位置失配时，他会跳到前一个最大匹配，
因此aaaa在中间找不到aaa这个匹配时，直接向下跳到nxt[nxt[len]]，就可以照顾到中间的字符串。

代码

#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1e6+7;

int j,nxt[maxn],len,vis[maxn];
string str;

signed main(){
    cin>>str;
    j=-1;nxt[0]=-1;
    len=str.length();
    for(int i=0;i<len;i++){  //获取失配数组 
        j=nxt[i];
        while(j!=-1&&str[i]!=str[j]) j=nxt[j];
        nxt[i+1]=(str[i]==str[j])?j+1:0; 
    }
    for(int i=1;i<len;i++){
        vis[nxt[i]]++; //记录最大后缀数出现的次数 
    }
    int ans=nxt[len];
    if(vis[ans]&&ans>0){ //中间存在最大后缀 
        cout<<str.substr(0,ans)<<endl;
    }else if(nxt[ans]>0){ //下跳到下一个后缀，比如aaaa这种清空 
        cout<<str.substr(0,nxt[ans])<<endl;
    }else cout<<"Just a legend"<<endl; //其余情况 
    return 0; 
}