Suffix Sort

Suffix Array

后缀数组是什么呢，懒得说了，直接上概念吧．

后缀数组$sa[i]$就表示排名为i的后缀的起始位置的下标

它的映射数组$rk[i]$就表示起始位置的下标为i的后缀的排名

简单来说，sa表示排名为i的是啥，rk表示第i个的排名是啥

等待填坑

#include <cstdio>
#include <cstring>
#include <algorithm>

#define RI register int

using namespace std;

const int CF = 1e6 + 10;

char s[CF];
int N, M, rak[CF], sa[CF], tax[CF], tp[CF];

inline void qsort() {
    for (RI i = 0; i <= M; ++i) tax[i] = 0;
    for (RI i = 1; i <= N; ++i) ++tax[rak[i]];
    for (RI i = 1; i <= M; ++i) tax[i] += tax[i - 1];
    for (RI i = N; i >  0; --i) sa[tax[rak[tp[i]]]--] = tp[i];
}

inline void suffixsort() {
    M = 75;
    for (RI i = 1; i <= N; ++i) rak[i] = s[i] - '0' + 1, tp[i] = i;
    qsort();
    for (RI w = 1, p = 0; p < N; M = p, w <<= 1) {
        p = 0;
        for (RI i = 1; i <= w; ++i) tp[++p] = N - w + i;
        for (RI i = 1; i <= N; ++i) if (sa[i] > w) tp[++p] = sa[i] - w;
        qsort();
        swap(tp, rak);
        rak[sa[1]] = p = 1;
        for (RI i = 2; i <= N; ++i)
            rak[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
    }
    for (RI i = 1; i <= N; ++i) printf("%d ", sa[i]);
}

int main() {
    scanf("%s", s + 1);
    N = strlen(s + 1);
    suffixsort();
}