P3426.cpp

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
const int N = 5e5+10, INF = 1e9;
int n, fail[N], suf[N], pre[N], mxdis = 1, ans = INF;
vector<int> G[N];
bool mark[N];

void del(int u) {
    int p = pre[u], s = suf[u];
    suf[p] = s;
    pre[s] = p;
    pre[u] = suf[u] = INF;
    if (p != 0 && s != n+1) mxdis = max(mxdis, s-p);
}

void deltree(int u) {
    if (u) del(u);
    for (int to: G[u]) {
        if (!mark[to]) deltree(to);
    }
}

void dfs(int u) {
    deltree(u);

    for (int to: G[u]) {
        if (mark[to]) {
            if (mxdis <= to) {
                ans = min(ans, to);
            }
            dfs(to);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string s;
    cin >> s;
    n = s.size();
    s = ' ' + s;
    
    for (int i = 2; i <= n; i++) {
        fail[i] = fail[i-1];
        while (fail[i] && s[fail[i]+1] != s[i]) fail[i] = fail[fail[i]];
        if (s[fail[i]+1] == s[i]) fail[i]++;
    }

    for (int i = 1; i <= n; i++) G[fail[i]].pb(i);
    for (int j = n; j; j = fail[j]) mark[j] = true;

    for (int i = 0; i <= n+1; i++) {
        pre[i] = i-1;
        suf[i] = i+1;
    }
    dfs(0);
    cout << ans << '\n';
    return 0;
}