代码：

KMP：

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
char s[N];
int nex[N];inline void kmp(){int n=strlen(s+1);int j=0;nex[1]=0;for(int i=2;i<=n;i++){while(j&&s[j+1]!=s[i]) j=nex[j];if(s[j+1]==s[i]) j++;nex[i]=j;}int maxx=-1;for(int i=2;i<=n-1;i++) maxx=max(maxx,nex[i]);j=nex[n];while(j>maxx) j=nex[j];if(!j) cout<<"Just a legend";else{for(int i=1;i<=j;i++) cout<<s[i];}
}int main(){cin>>s+1;kmp();
}

EXKMP：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n;
int z[N];
char s[N];void exkmp(){n=strlen(s+1);int L=1,R=0;z[1]=0;for(int i=2;i<=n;i++){if(i>R) z[i]=0;else{int k=i-L+1;z[i]=min(z[k],R-i+1);}while(i+z[i]<=n&&s[z[i]+1]==s[z[i]+i]) z[i]++;if(i+z[i]-1>R) L=i,R=i+z[i]-1;}int ans=0,x=0;for(int i=1;i<=n;i++){if(i+z[i]-1==n)if(x>=z[i])ans=max(ans,z[i]);x=max(x,z[i]);}if(!ans) cout<<"Just a legend\n";elsefor(int i=1;i<=ans;i++) cout<<s[i];
}int main(){scanf("%s",s+1);exkmp();
}