[luoguP3809]后缀排序

题意

给定一个字符串，要求将它的所有后缀按照字典序排序，并按顺序输出每个后缀第一个字符的下标。

sol

这是后缀数组（Suffix Array, SA）的板子题。
我们定义：
\(s_{i\cdots j}\) 表示 \(s\) 中下标在 \(i\) 到 \(j\) 之间的子串。
\(sa_i\) 表示排名为 \(i\) 的后缀第一个字符的下标；
\(rk_i\) 表示第一个字符下标为 \(i\) 的后缀的排名。
而本题就是计算 \(sa\) 数组。
最朴素的做法即为将所有后缀进行一次排序，时间复杂度 \(O(n^2\log n)\)，这显然是远远不足的，我们需要对其优化。
下面介绍一种倍增的方法，可以 \(O(n\log n)\) 地计算出 \(sa\) 数组。
首先根据所有长度为 \(1\) 的子串对 \(s\) 进行排序，即根据每个字符进行排序。当我们对所有长度为 \(w\) 的子串排序之后，我们将每个后缀的长度为 \(2w\) 的前缀分为长度为 \(w\) 的两部分，根据之前得到的信息对这个后缀进行排序，直到所有数都排列完毕。
使用基数排序可以将复杂度优化到 \(O(n\log n)\)。

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1000005;

char s[N];
int n;
int sa[N], rk[N], oldrk[N], cnt[N], scd[N];

void get_sa(){
    for (int i = 1; i <= n; i ++ ) cnt[rk[i] = s[i]] ++ ;
    for (int i = 1; i <= 128; i ++ ) cnt[i] += cnt[i - 1];
    for (int i = n; i; i -- ) sa[cnt[rk[i]] -- ] = i;
    for (int w = 1, m = 128, p = 0; ; m = p, p = 0, w <<= 1){
        for (int i = n - w + 1; i <= n; i ++ ) scd[ ++ p] = i;
        for (int i = 1; i <= n; i ++ ) 
            if (sa[i] > w) scd[ ++ p] = sa[i] - w;
        memset(cnt, 0, m + 1 << 2);
        memcpy(oldrk, rk, n + 1 << 2);
        for (int i = 1; i <= n; i ++ ) cnt[rk[i]] ++ ;
        for (int i = 1; i <= m; i ++ ) cnt[i] += cnt[i - 1];
        for (int i = n; i; i -- ) sa[cnt[rk[scd[i]]] -- ] = scd[i];

        p = 0;
        for (int i = 1; i <= n; i ++ ) rk[sa[i]] = (oldrk[sa[i - 1]] == oldrk[sa[i]] && oldrk[sa[i - 1] + w] == oldrk[sa[i] + w]) ? p : ++ p;
        if (p >= n) return ;
    }
}

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

    get_sa();

    for (int i = 1; i <= n; i ++ ) printf("%d ", sa[i]);

    return 0;
}