Suffix Array

#include <cstdio>
#include <cstring>

using namespace std;

struct node {
    int a, b, id;
};

const int N = 100010;

int n;
char s[N];
int cnt[N], sa[N], rk[N * 2], height[N], h[N];
node p[N], q[N];

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = 1; i <= n; ++i)
        cnt[s[i] - 'a'] = 1;
    for (int i = 1; i < 26; ++i)
        cnt[i] += cnt[i - 1];
    for (int i = 1; i <= n; ++i)
        rk[i] = cnt[s[i] - 'a'];
    for (int l = 1; l < n; l <<= 1) {
        for (int i = 1; i <= n; ++i) {
            p[i].id = i;
            p[i].a = rk[i];
            p[i].b = rk[i + l];
        }
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; ++i)
            ++cnt[p[i].b];
        for (int i = 1; i <= n; ++i)
            cnt[i] += cnt[i - 1];
        for (int i = n; i; --i)
            q[cnt[p[i].b]--] = p[i];
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; ++i)
            ++cnt[q[i].a];
        for (int i = 1; i <= n; ++i)
            cnt[i] += cnt[i - 1];
        for (int i = n; i; --i)
            p[cnt[q[i].a]--] = q[i];
        for (int i = 1; i <= n; ++i) {
            rk[p[i].id] = rk[p[i - 1].id];
            if (p[i].a != p[i - 1].a || p[i].b != p[i - 1].b)
                ++rk[p[i].id];
        }
    }
    for (int i = 1; i <= n; ++i)
        sa[rk[i]] = i;
    for (int i = 1; i < n; ++i)
        printf("%d ", sa[i]);
    printf("%d\n", sa[n]);
    for (int i = 1; i <= n; ++i) {
        h[i] = h[i - 1] - 1;
        if (h[i] < 0)
            h[i] = 0;
        while (s[i + h[i]] == s[sa[rk[i] - 1] + h[i]])
            ++h[i];
    }
    for (int i = 1; i <= n; ++i)
        height[rk[i]] = h[i];
    for (int i = 2; i < n; ++i)
        printf("%d ", height[i]);
    if (n > 1)
    printf("%d\n", height[n]);
    return 0;
}