13264번: 접미사 배열 2

https://www.acmicpc.net/problem/13264

앞에서부터 1, 2, 4, ...개를 보며 계수 정렬하는 풀이
http://www.geeksforgeeks.org/suffix-array-set-2-a-nlognlogn-algorithm/

시간복잡도는 $O(n\lg n)$

#include<cstdio>
#include<cstring>
char s[100001];
int r[100000], t[100000], sa[100000], c[100000], n, sz;
void csort() {
    for (int i = 0; i < sz; i++) c[i] = 0;
    for (int i = 0; i < n; i++) c[r[i]]++;
    for (int i = 1; i < sz; i++) c[i] += c[i - 1];
    for (int i = n; i--;) sa[--c[r[t[i]]]] = t[i];
}
int main() {
    scanf("%s", s);
    n = strlen(s);
    sz = 128 < n ? n : 128;
    for (int i = 0; i < n; i++) r[i] = s[i], t[i] = i;
    csort();
    for (int i = 1, k; i < n; i <<= 1) {
        k = 0;
        for (int j = n - i; j < n; j++) t[k++] = j;
        for (int j = 0; j < n; j++) if (sa[j] >= i) t[k++] = sa[j] - i;
        csort();
        k = 0;
        for (int j = 0; j < n; j++) t[sa[j]] = !j || sa[j] + i < n && sa[j - 1] + i < n &&r[sa[j]] == r[sa[j - 1]] && r[sa[j] + i] == r[sa[j - 1] + i] ? k : ++k;
        for (int j = 0; j < n; j++) r[j] = t[j];
    }
    for (int i = 0; i < n; i++) printf("%d\n", sa[i]);
    return 0;
}