「JSOI2019」节日庆典

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

const int MAXN = 3e6 + 5;

char s[MAXN];
int next[MAXN];
int st1[MAXN], st2[MAXN], cnt1, cnt2;
int *x = st1, *y = st2;

void exKMP_pre(char *T) {
    int n = strlen(T);
    next[0] = n;
    int p = 0;
    while (p + 1 < n && T[p] == T[p + 1]) p++;
    next[1] = p;
    int k = 1;
    for (int x = 2; x < n; ++x) {
        p = k + next[k] - 1;
        int l = next[x - k];
        if (x + l <= p) next[x] = l;
        else {
            int j = p - x + 1;
            if (j < 0) j = 0;
            while (x + j < n && T[x + j] == T[j]) j++;
            next[x] = j;
            k = x;
        }
    }
}

int cmp(int p, int q, int k) {
    int t = p + k - q + 1;
    if (next[t] < k - t + 1) {
        if (s[next[t]] < s[t + next[t]]) return 1;
        else return -1;
    }
    t = q - p;
    if (next[t] < p) {
        if (s[next[t]] < s[t + next[t]]) return -1;
        else return 1;
    }
    return 0;
}

int main() {
    scanf("%s", s);
    exKMP_pre(s);
    int n = strlen(s);
    for (int i = 0; i < n; ++i) {
        x[++cnt1] = i;
        for (int k = 1; k <= cnt1; ++k) {
            int q = x[k];
            if (cnt2 == 0) {
                y[++cnt2] = q;
                continue;
            }
            int p = y[cnt2];
            if (s[i] > s[p + i - q]) continue;
            if (s[i] < s[p + i - q]) {
                y[cnt2 = 1] = q;
                continue;
            }
            if (s[i] == s[p + i - q]) {
                if (p + i - q < q) y[++cnt2] = q;
                continue;
            }
        }
        swap(x, y);
        cnt1 = cnt2, cnt2 = 0;
        int ans = x[1];
        for (int k = 2; k <= cnt1; ++k) {
            if (cmp(ans, x[k], i) == 1) ans = x[k];
        }
        printf("%d ", ans + 1);
    }
    return 0;
}