后缀排序

#include <cstdio>
#include <cstring>

const int N = 1e6 + 5;
char c[N];
int n, m, b[N], rk[N], tp[N], sa[N];
//rk 第i个后缀的排名
//sa 排名为i的后缀

void Rsort() {
    memset(b + 1, 0, m * 4);
    for (int i = 1; i <= n; ++i) 
        b[rk[i]]++;
    for (int i = 2; i <= m; ++i) 
        b[i] += b[i-1];
    for (int i = n; i >= 1; --i)
        sa[b[rk[tp[i]]]--] = tp[i];
}

int main() {
    scanf("%s", c + 1);
    n = strlen(c + 1); m = 75;
    for (int i = 1; i <= n; ++i)
        rk[i] = c[i] - '0' + 1, tp[i] = i;
    Rsort();
    for (int w = 1, p = 0; p < n; m = p, w *= 2) {
        p = 0;
        for (int i = n - w + 1; i <= n; ++i)
            tp[++p] = i;
        for (int i = 1; i <= n; ++i)
            if (sa[i] > w) tp[++p] = sa[i] - w;
		//tp 按第w-2w排序后排名为i的后缀
        Rsort();
        memcpy(tp + 1, rk + 1, n * 4);
		//tp 按前w个排序后第i个后缀的排名
        p = rk[sa[1]] = 1;
        for (int i = 2; i <= n; ++i)
            rk[sa[i]] = (tp[sa[i]] == tp[sa[i-1]] && tp[sa[i]+w] == tp[sa[i-1]+w]) ? p : ++p;
    }
    for (int i = 1; i <= n; ++i)
        printf("%d ", sa[i]);
    return 0;
}