1. 题目

传送门=￣ω￣=

2. 题解

首先只出现了一次 => Right 集合大小=1

就搞个 SAM，建出 pre 树，对于一个 Right 集合大小=1 的点 a：

它的 endpos 唯一，设为 $x$，那么这个状态的最长子串（$maxlen$）一定是 $[1, x]$这个前缀。

且它的最短子串（$minlen$）等于其 pre 树的父亲的 $maxlen+1$

所以在 $[1,maxlen-minlen]$内，第 $i$个位置的最小值可以被 $mxl-i+1$更新

在 $[maxlen-minlen+1, maxlen]$内，第 $i$个位置的最小值可以被 $minlen$更新

第一个用一个后缀最小值维护就行了

第二个用线段树维护 QwQ

代码：

#include <bits/stdc++.h>

#define NS (500005)
#define LS(a) (a << 1)
#define RS(a) (a << 1 | 1)

using namespace std;

char str[NS];

int n, suf[NS], t[NS << 2];

void Upd1(int a, int v) {suf[a] = min(suf[a], v);}

void Upd2(int l, int r, int v, int L, int R, int a)
{
    v = min(t[a], v);
    if (l <= L && R <= r) {t[a] = min(t[a], v); return;}
    int Mid = (L + R) >> 1;
    if (l <= Mid) Upd2(l, r, v, L, Mid, LS(a));
    if (r > Mid) Upd2(l, r, v, Mid + 1, R, RS(a));
}

void Cal(int L, int R, int a)
{
    if (L == R) {suf[L] = min(suf[L], t[a]); return;}
    t[LS(a)] = min(t[LS(a)], t[a]), t[RS(a)] = min(t[RS(a)], t[a]);
    int Mid = (L + R) >> 1;
    Cal(L, Mid, LS(a)), Cal(Mid + 1, R, RS(a));
}

struct SAM
{
    struct N
    {
        map<int, int> nxt;
        int fa, mxl, sz;
        int& operator [] (const char c) {return nxt[c - 'a'];}
    } e[NS << 1];
    int sz, lst;
    vector<int> g[NS << 1];
    SAM() {sz = lst = 1;}
    void insert(char c)
    {
        int a = ++sz, p = lst;
        e[a].sz = 1, e[a].mxl = e[p].mxl + 1, lst = a;
        while (p && !e[p][c]) e[p][c] = a, p = e[p].fa;
        if (!p) {e[a].fa = 1; return;}
        int q = e[p][c];
        if (e[q].mxl == e[p].mxl + 1) {e[a].fa = q; return;}
        int nq = ++sz;
        e[nq] = e[q], e[nq].sz = 0, e[nq].mxl = e[p].mxl + 1;
        e[q].fa = e[a].fa = nq;
        while (e[p][c] == q) e[p][c] = nq, p = e[p].fa;
    }
    void Dfs(int a)
    {
        for (int i = 0; i < g[a].size(); i += 1)
            Dfs(g[a][i]), e[a].sz += e[g[a][i]].sz;
    }
    void run()
    {
        for (int i = 2; i <= sz; i += 1) g[e[i].fa].push_back(i);
        Dfs(1);
        for (int i = 2; i <= sz; i += 1)
            if (e[i].sz == 1)
            {
                Upd1(e[i].mxl - e[e[i].fa].mxl - 1, e[i].mxl + 1);
                Upd2(e[i].mxl - e[e[i].fa].mxl, e[i].mxl, e[e[i].fa].mxl + 1,
                    1, n, 1);
            }
        for (int i = n - 1; i >= 1; i -= 1)
            suf[i] = min(suf[i], suf[i + 1]);
        for (int i = 1; i <= n; i += 1) suf[i] -= i;
        Cal(1, n, 1);
        for (int i = 1; i <= n; i += 1)
            printf("%d\n", suf[i]);
    }
} sam;

int main(int argc, char const* argv[])
{
    memset(suf, 127, sizeof(suf)), memset(t, 127, sizeof(t));
    scanf("%s", str + 1), n = strlen(str + 1);
    for (int i = 1; i <= n; i += 1) sam.insert(str[i]);
    sam.run();
    return 0;
}