kmp中的next数组表示按照当前位置结尾的相同的最大真前缀和后前缀长度
那么如果这玩意真的存在,那么next[n] 一定不为零
然后枚举一下2-n-1,找找有没有相等的next就可以了
#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
using namespace std;
template<class T>inline void read(T &x)
{
x=0;register char c=getchar();register bool f=0;
while(!isdigit(c))f^=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(f)x=-x;
}
template<class T>inline void print(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar('0'+x%10);
}
char s[1000006];
int ne[1000006];
int ma;
int main(){
ios::sync_with_stdio(false);
scanf("%s",s+1);
int l=strlen(s+1);
int f=0;
for(int i=2;i<=l;++i){
while(f&&s[i]!=s[f+1]) f=ne[f];
if(s[i]==s[f+1]) f++;
ne[i]=f;
if(i!=l)
ma=max(ma,ne[i]);
}
f=l;
//cout<<ma<<endl;
if(ne[l]==0){
cout<<"Just a legend";
return 0;
}else{
while(ne[f]>ma) f=ne[f];
f=ne[f];
if(f==0){
cout<<"Just a legend";
return 0;
}else{
for(int i=2;i<l;++i){
if(ne[i]==f){
for(int j=i-ne[i]+1;j<=i;++j){
cout<<s[j];
}
return 0;
}
}
}
}
return 0;
}