9248번: Suffix Array

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

suffix array와 LCP를 구하는 문제

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

#include<cstdio>
#include<cstring>
int n, sz, a[500000], b[500000], sa[500000], c[500000], lcp[500000];
char s[500001];
void csort() {
    for (int i = 0; i < sz; i++) c[i] = 0;
    for (int i = 0; i < n; i++) c[a[i]]++;
    for (int i = 1; i < sz; i++) c[i] += c[i - 1];
    for (int i = n; i--;) sa[--c[a[b[i]]]] = b[i];
}
void SA() {
    sz = n > 128 ? n : 128;
    for (int i = 0; i < n; i++) a[i] = s[i], b[i] = i;
    csort();
    for (int i = 1, k; i <= n; i <<= 1) {
        k = 0;
        for (int j = n - i; j < n; j++) b[k++] = j;
        for (int j = 0; j < n; j++) if (sa[j] >= i) b[k++] = sa[j] - i;
        csort();
        k = 0;
        for (int j = 0; j < n; j++) b[sa[j]] = !j || sa[j] + i < n && sa[j - 1] + i < n&&a[sa[j]] == a[sa[j - 1]] && a[sa[j] + i] == a[sa[j - 1] + i] ? k : ++k;
        for (int j = 0; j < n; j++) a[j] = b[j];
    }
}
void LCP() {
    for (int i = 0, j = 0; i < n; lcp[a[i++]] = j ? j-- : 0)
        while (a[i] && s[i + j] == s[sa[a[i] - 1] + j]) j++;
}
int main() {
    scanf("%s", s);
    n = strlen(s);
    SA();
    LCP();
    for (int i = 0; i < n; i++) printf("%d ", sa[i] + 1);
    printf("\nx");
    for (int i = 1; i < n; i++) printf(" %d", lcp[i]);
    return 0;
}