Jisoo

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;
}