def kmp(s):
n = len(s)
prefix = [0 for _ in range(n)]
for i in range(1, n):
j = prefix[i - 1]
while j > 0 and s[i] != s[j]:
j = prefix[j - 1]
if s[i] == s[j]:
j += 1
prefix[i] = j
return prefix
if __name__ == '__main__':
s = input()
prefix = kmp(s)
answer = prefix[-1]
if answer == 0:
print("Just a legend")
elif prefix.count(answer) >= 2:
print(s[0:answer])
else:
answer = prefix[answer - 1]
if answer == 0:
print("Just a legend")
else:
print(s[0:answer])
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
int main(){
string s;
cin>>s;
ll n =s.length();
ll kmp[n]={};
ll pointer=0;
kmp[0]=0;
ll cnt[n+3]={};
//cout<<n<<endl;
for (int i =1;i<n;i++){
pointer= kmp[i-1];
while (pointer!=0&&s[i]!=s[pointer]){
pointer=kmp[pointer-1];
//cout<<pointer<<endl;
}
kmp[i]=pointer + (s[i]==s[pointer]);
}
bool check[n]={};
pointer=n;
vector<int> ans;
while (pointer>0){
ans.push_back(pointer);
pointer=kmp[pointer-1];
}
/*for (int i =0 ;i<n;i++){
cout<<kmp[i]<<" ";
}
cout<<endl;*/
for (int i =0;i<n+1;i++){
cnt[i]++;
}
for (int i =n;i>0;i--){
cnt[kmp[i-1]]+=cnt[i];
}
//cout<<ans.size()<<"\n";
int mx=INT_MIN;
for (int i =0;i<ans.size();i++){
if (cnt[ans[i]]>=3){
mx=max(mx,ans[i]);
}
}
if (mx==INT_MIN){
cout<<"Just a legend";
}else cout<<s.substr(0,mx);
}
450A - Jzzhu and Children | 546A - Soldier and Bananas |
32B - Borze | 1651B - Prove Him Wrong |
381A - Sereja and Dima | 41A - Translation |
1559A - Mocha and Math | 832A - Sasha and Sticks |
292B - Network Topology | 1339A - Filling Diamonds |
910A - The Way to Home | 617A - Elephant |
48A - Rock-paper-scissors | 294A - Shaass and Oskols |
1213A - Chips Moving | 490A - Team Olympiad |
233A - Perfect Permutation | 1360A - Minimal Square |
467A - George and Accommodation | 893C - Rumor |
227B - Effective Approach | 1534B - Histogram Ugliness |
1611B - Team Composition Programmers and Mathematicians | 110A - Nearly Lucky Number |
1220B - Multiplication Table | 1644A - Doors and Keys |
1644B - Anti-Fibonacci Permutation | 1610A - Anti Light's Cell Guessing |
349B - Color the Fence | 144A - Arrival of the General |