题目描述

求一个最长的子串，满足下面三个性质

1. 子串是原串的前缀
2. 子串是原串的后缀
3. 除了前缀和后缀，还在其他地方出现过一次

思路

首先，这个答案子串肯定是原串的border，那么我们就把$nxt[n]\dots nxt[nxt[n]]\dots nxt[\dots nxt[n]]nxt[n]\; \backslash dots\; nxt[nxt[n]]\; \backslash dots\; nxt[\backslash dots\; nxt[n]]$ 都计算出来，这样就知道原串的所有border

知道这个后，我们就可以从大到小贪心的来求，首先判断$nxt[n]nxt[n]$行不行，判断可行的方法，就是的$nxt[i]==nxt[n]nxt[i]\; ==\; nxt[n]$，这样说明这个$nxt[n]nxt[n]$也在中间出现过 如果$nxt[n]nxt[n]$不行，我们接着判断$nxt[nxt[n]]nxt[nxt[n]]$，以此类推

代码

/**
 *    author: andif
 *    created: 11.06.2023 00:43:57
**/
#include<bits/stdc++.h>
using namespace std;

#define de(x) cerr << #x << " = " << x << endl
#define dd(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a; i > b; --i)
#define mt(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)a.size()
#define fi first
#define se second
#define qc ios_base::sync_with_stdio(0);cin.tie(0)
#define eb emplace_back
#define all(a) a.begin(), a.end()
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using vi = vector<int>;
const db eps = 1e-9;

vi get_next(string s) {
    int n = sz(s) - 1;
    vi nxt(n + 1);
    rep(i, 2, n + 1) {
        int j = i - 1;
        while(j && s[nxt[j] + 1] != s[i]) j = nxt[j];
        if (j) {
            nxt[i] = nxt[j] + 1;
        } else {
            nxt[i] = 0;
        }
    }
    return nxt;
}
int main() {
    string s; cin >> s;
    s = "#" + s;
    int n = sz(s) - 1;
    if (n == 1) {
        cout << "Just a legend" << '\n';
        return 0;
    }
    vi nxt = get_next(s);
    // rep(i, 1, n + 1) dd(i), de(nxt[i]);
    vi cnt(n + 1);
    rep(i, 2, n) cnt[nxt[i]]++;

    vi fg(n + 1);
    int k = n;
    while(nxt[k]) {
        fg[nxt[k]] = 1;
        k = nxt[k];
    }

    int ans = -1;
    per(i, n - 2, 0) {
        if (fg[i] && cnt[i]) {
            ans = i;
            break;
        }
    }
    if (~ans) {
        cout << s.substr(1, ans) << '\n';
    } else {
        cout << "Just a legend" << '\n';
    }
    return 0;
}