「SNOI2019」字符串

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

const int MAXN = 1e6 + 5;

int n;
char s[MAXN];
int lcp[MAXN];  // lcp(i, i+1)
int ans[MAXN];

bool cmp(int x, int y) {
    int i = x, j = y;
    if (i > j)
        swap(i, j);
    int t = lcp[i];
    if (t >= j - i) {
        if (x < y)
            return 1;
        else
            return 0;
    }
    if (s[i + t + 1] < s[i + t]) {
        if (i == x)
            return 1;
        else
            return 0;
    }
    if (i == x)
        return 0;
    else
        return 1;
}

int main() {
    scanf("%d", &n);
    scanf("%s", s + 1);
    lcp[n] = 0;
    for (int i = n - 1; i >= 1; --i) {
        if (s[i] == s[i + 1])
            lcp[i] = lcp[i + 1] + 1;
        else
            lcp[i] = 0;
    }
    for (int i = 1; i <= n; ++i) ans[i] = i;
    sort(ans + 1, ans + n + 1, cmp);
    for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
    return 0;
}