Asterix，Obelix和他们的临时伙伴Suffix、Prefix已经最终找到了和谐寺。然而和谐寺大门紧闭，就连Obelix的运气也没好到能打开它。

不久他们发现了一个字符串S（|S|<=1000000），刻在和谐寺大门下面的岩石上。Asterix猜想那一定是打开寺庙大门的密码，于是就大声将字符串朗读了出来，然而并没有什么事发生。于是Asterix又猜想密码一定是字符串S的子串T。

Prefix认为T是S的前缀，Suffix认为T是S的后缀，Obelix却认为T应该是S中的某一部分，也就是说，T既不是S的前缀，也不是S的后缀。

Asterix选择子串T来满足所有伙伴们的想法。同时，在所有可以被接受的子串变形中，Asterix选择了最长的一个（因为Asterix喜欢长的字符串）当Asterix大声读出子串T时，寺庙的大门开了。 （也就是说，你需要找到既是S的前缀又是S的后缀同时又在S中间出现过的最长子串）

现在给你字符串S，你需要找到满足上述要求的子串T。

输入格式：

一个长度在[1,1000000]间的只包含小写字母的字符串S。

输出格式：

输出子串T，如果T不存在，输出 "Just a legend"，不包含引号。

后缀数组解法：（TLE）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;
const int inf = 1e9;
int rak[maxn], sa[maxn];
int tx[maxn], height[maxn];
int n, m, p;
char s[maxn];
int lcp[maxn], L[maxn];
struct node {
    int x, y, id;
}a[maxn], b[maxn];
void rsort() {
    for (int i = 1; i <= m; i++) tx[i] = 0;
    for (int i = 1; i <= n; i++) tx[a[i].y]++;
    for (int i = 1; i <= m; i++) tx[i] += tx[i - 1];
    for (int i = 1; i <= n; i++) b[tx[a[i].y]--] = a[i];
    for (int i = 1; i <= m; i++) tx[i] = 0;
    for (int i = 1; i <= n; i++) tx[b[i].x]++;
    for (int i = 1; i <= m; i++) tx[i] += tx[i - 1];
    for (int i = n; i >= 1; i--) a[tx[b[i].x]--] = b[i];
}

void ssort() {
    rsort();
    p = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i].x != a[i - 1].x || a[i].y != a[i - 1].y) ++p;
        rak[a[i].id] = p;
    }
    for (int i = 1; i <= n; i++) {
        a[i].x = rak[i];
        a[i].id = sa[rak[i]] = i;
        a[i].y = 0;
    }
    m = p;
}

void solve() {
    m = 127;
    for (int i = 1; i <= n; i++) {
        a[i].x = a[i].y = s[i];
        a[i].id = i;
    }
    ssort();
    for (int j = 1; j <= n; j <<= 1) {
        for (int i = 1; i + j <= n; i++) {
            a[i].y = a[i + j].x;
        }
        ssort();
        if (p == n)break;
    }
}

void getHeight() {
    int k = 0;
    for (int i = 1; i <= n; i++) {
        if (k) k--;
        int j = sa[rak[i] - 1];
        while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
        height[rak[i]] = k;
    }
}

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    solve();
    getHeight();
    int mm = 1e9;
    lcp[1] = n;
    for (int i = rak[1] + 1; i <= n; i++) {
        mm = min(height[i], mm);
        lcp[sa[i]] = mm;
    }
    mm = 1e9;
    for (int i = rak[1]; i >= 1; i--) {
        mm = min(height[i], mm);
        lcp[sa[i - 1]] = mm;
    }
    int ans = 0;
    for (int i = n, j = 1; i > 1; i--, j++) {
        L[j] = L[j - 1];
        ans = max(ans, min(L[j - 1], L[lcp[i]]));
        if (n - i + 1 == lcp[i]) {
            L[j] = lcp[i];
        }
    }
    if (!ans) {
        printf("Just a legend\n"); return 0;
    }
    for (int i = 1; i <= ans; i++) {
        printf("%c", s[i]);
    }
    return 0;
}

扩展KMP解法：（AC）

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e6 + 5;
int lcp[maxn], L[maxn];
int t[maxn], tot;
char s[maxn];
int main(){
    scanf("%s",s);
    int n = strlen(s);
    for(int i = 1, mx = 0, l = 0; s[i]; i++){
        lcp[i]=i<mx?min(mx-i,lcp[i-l]): 0;
        while(s[lcp[i]]==s[i+lcp[i]])lcp[i]++;
        if(i+lcp[i]>mx)mx=i+lcp[i],l=i;
    }
    lcp[0] = n;
    for (int i = n - 1; i >= 0; i--) lcp[i + 1] = lcp[i];
    for (int i = 1; i <= n; i++) {
        cout << lcp[i] << " ";
    }
    cout << endl;
    int ans = 0;
    for (int i = n, j = 1; i > 1; i--, j++) {
        L[j] = L[j - 1];
        ans = max(ans, min(L[j - 1], L[lcp[i]]));
        if (n - i + 1 == lcp[i]) {
            t[++tot] = lcp[i];
            L[j] = lcp[i];
        }
    }
    if (!ans) {
        printf("Just a legend\n"); return 0;
    }
    for (int i = 0; i < ans; i++) {
        printf("%c", s[i]);
    }
    return 0;
}