\(\mathscr{Description}\)

??Link.

??给定字符串 \(S\)，求 \(S\) 的每个前缀的最小表示法起始下标（若有多个，取最小的）。

??\(|S|\le3\times10^6\)。

\(\mathscr{Solution}\)

??注意到一个显然的事实，对于某个前缀 \(S[:i]\) 以及两个起始下标 \(p,q\)，若已有 \(S[p:i]，那么在所有的 \(j>i\) 中，都有 \(S[p:j]。换言之，最终 \(i\) 的答案 \(r_i\) 必然满足 \(r_i\in B_i=\arg\min_{p\le i}\{S[p:i]\}\)，同时有 \(B_{i+1}\subseteq B_i\cup\{i+1\}\)，故我们可以通过去除 \(B_i\cup\{i+1\}\) 中不优秀的起始位置来得到 \(B_{i+1}\)。

??可惜，\(|B_m|=\mathcal O(m)\) 的，需要进一步精简。这提示我们反思“\(S[p:i]\) 取最小”是否是“\(p\) 可能成为 \(r_i\)”的充要条件。答案是否定的。考虑后缀 \(S[p:i]\) 和 \(S[q:i]~(p，若 \(p,q\in B_i\)，有 \(S[p:p+i-q+1]=S[q:i]\)，即 \(S[q:i]\) 是 \(S[p:i]\) 的一个 border。由 border 的相关性质，自然地想到研究 \(|S[q:i]|>\frac{|S[p:i]|}{2}\) 的情况，此时 \(S[p:i]\) 有周期 \(T=|S[p:i]|-|S[q:i]|\)（周期可能不完整）。取 \(S[r:i]\) 为最后一个不完整（或恰好完整）的周期，可以说明：\(S[p:i]\) 不同时大于 \(S[q:i]\) 和 \(S[r:i]\)。如图：

??若我们想让 \(S[p:i]，就需要在后缀加一个字符 \(S_{i+1}=x\)（红点），使得 \(x>y\)（蓝点），但一旦有 \(y，就能让最后一个周期 \(S[r:i]\) 带上红点一路走到 \(S[p:i]\) 的开头，得到 \(S[r:i+1]，故结论成立。?\(\square\)

??据此维护出不存在满足上述 \(p,q\) 关系的新集合 \(B_i'\subseteq B_i\)，显然 \(|B_m'|=\mathcal O(\log m)\)，所以维护总过程是 \(\mathcal O(n\log n)\) 的。

??此外，求答案 \(r_i\) 时，仍然有必要枚举 \(B_i'\) 中的每个下标取优。利用前缀相等的性质，发现我们仅需要完成 \(S\) 子串与 \(S\) 前缀的快速比较，那么用 Z-function 可以做到 \(\mathcal O(1)\)。综上，最终复杂度为 \(\mathcal O(n\log n)\)。

\(\mathscr{Code}\)

/*+Rainybunny+*/

#include 

#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)
#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)

inline void wint(const int x) {
    if (9 < x) wint(x / 10);
    putchar(x % 10 ^ '0');
}

const int MAXN = 3e6, MAXG = 100;
int n, z[MAXN + 5];
char s[MAXN + 5];
int gcnt, good[MAXG + 5]; // indices that may be the answer.

inline void calcZ() {
    z[1] = n;
    for (int i = 2, l = 0, r = 0; i <= n; ++i) {
        if (i <= r) z[i] = std::min(z[i - l + 1], r - i + 1);
        while (i + z[i] <= n && s[i + z[i]] == s[1 + z[i]]) ++z[i];
        if (i + z[i] - 1 > r) r = i + z[l = i] - 1;
    }
}

inline void adapt(const int k) {
    auto compare = [&](const int u, const int v)->int {
        return u < v ?
          (s[u + k - v] == s[k] ? 0 : s[u + k - v] < s[k] ? -1 : 1)
          : (s[k] == s[v + k - u] ? 0 : s[k] < s[v + k - u] ? -1 : 1);
    };

    static int tmp[MAXG + 5]; rep (i, 1, gcnt) tmp[i] = good[i];
    int ocnt = gcnt, pst = good[gcnt]; good[gcnt = 1] = pst;
    per (i, ocnt - 1, 1) {
        if (int t = compare(pst, tmp[i]); t > 0) {
            good[gcnt = 1] = pst = tmp[i];
        } else if (!t) {
            pst = tmp[i];
            while (gcnt && k - good[gcnt] + 1 << 1 > k - pst + 1) --gcnt;
            good[++gcnt] = pst;
        }
    }
    std::reverse(good + 1, good + gcnt + 1);
}

inline int best(const int k) {
    // compare S[l:r] with S[:r-l+1].
    auto compare = [](const int l, const int r)->int {
        if (z[l] >= r - l + 1) return 0;
        return s[l + z[l]] < s[z[l] + 1] ? -1 : 1;
    };

    int ans = good[1];
    rep (i, 2, gcnt) {
        int cur = good[i];
        if (int f1 = compare(ans + k - cur + 1, k); f1 > 0) ans = cur;
        else if (!f1) {
            int f2 = compare(cur - ans + 1, cur - 1); // cur <> ans.
            if (f2 < 0) ans = cur;
        }
    }
    return ans;
}

int main() {
    scanf("%s", s + 1), n = strlen(s + 1), calcZ();

    rep (i, 1, n) {
        good[++gcnt] = i, adapt(i);
        wint(best(i)), putchar(i < n ? ' ' : '\n');
    }
    return 0;
}