https://www.luogu.com.cn/problem/CF126B

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long  ULL;
string s;
string ans;
const int maxn = 1e6 + 6;
ULL pw[maxn];
ULL Hash[maxn];

ULL h(int i, int len) {
    return Hash[i] - Hash[i + len] * pw[len];
}

int main () {
    cin >> s;
    
    pw[0] = 1;
    for (int i = 1;i <= maxn; i++) {
        pw[i] = pw[i - 1] * 131;
    }
    
    int lens = s.size();
    Hash[lens] = 0;
    for (int i = lens - 1;i >= 0; i--) {
        Hash[i] = Hash[i + 1] * 131 + s[i] ;
    }
    
    for (int len = 1; len < lens; len++ ) {
        if (h(0, len) == h(lens - len , len)){
            ULL num = h(0, len);
            for (int i = 1;i < lens - 1; i++) {
                if (h(i, len) == num) {
                    ans = s.substr(0,len);
                }else {
                    break;
                }
            }
        }
        else {
            break;
        }
    }
    if (ans == ""){
        cout << "Just a legend";
    }else{
        cout << ans;
    }
    return 0;
}