详解链接点此处。

只有一行看着太难受了，那就放一份完整代码吧。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
int n; char s[N];

int sa[N], rk[N], pre[N], cnt[N];
int x[N], y[N]; //令 x 表示第一关键字排序的结果，y 表示第二关键字排序的结果
void init_SA() {
    int v = 128;
    for (int i = 0; i <= v; i++) cnt[i] = 0;
    for (int i = 1; i <= n; i++) ++cnt[ x[i] = (int)s[i] ];     //初始以 ASCII 作为排序依据
    for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];          //计数排序，前缀和桶
    for (int i = n; i >= 1; i--) sa[ cnt[x[i]]-- ] = i;         //计数排序计算初始 sa 数组
    for (int len = 1; ; len <<= 1) {
        int tot = 0;
        for (int i = n - len + 1; i <= n; i++) y[++tot] = i;    //这些第二关键字默认为 -INF，直接平移到最前面
        for (int i = 1; i <= n; i++)    //注意 sa[i] 的含义是第 i 小的后缀编号，因此从小到大遍历是有序的，将它们按照第二关键字顺序插入即可
            if (sa[i] > len) y[++tot] = sa[i] - len;
        // y[i] 表示以第二关键字排序，第 i 小的后缀下标，则 x[y[i]] 表示再按照第一关键字排序的排名
        // 因此这里计数排序和开头有区别
        for (int i = 0; i <= v; i++) cnt[i] = 0;
        for (int i = 1; i <= n; i++) ++cnt[ x[i] ];
        for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--) sa[ cnt[x[y[i]]]-- ] = y[i], y[i] = 0;
        // 接下来需要更新新的 x 数组，且需要使用之前的 x 数组。
        // 因此可以直接把 x 和 y 交换，接下来 y 代表 old_x
        swap(x, y), tot = 0;
        for (int i = 1; i <= n; i++) {
            if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + len] == y[sa[i - 1] + len]) x[sa[i]] = tot;
            else x[sa[i]] = ++tot;
        }
        v = tot;
        if (v == n) break;  //排好序了
    }
}

int ht[N];
void init_height() {
    for (int i = 1; i <= n; i++) rk[sa[i]] = i;
    for (int i = 1, j = 0, now = 0; i <= n; i++) {
        if (rk[i] == 1) { ht[rk[i]] = 0; continue; }
        j = sa[rk[i] - 1]; now = max(now - 1, 0);
        while (i + now <= n && j + now <= n && s[i + now] == s[j + now]) now++;
        ht[rk[i]] = now;
    }
}

int main() {
    scanf("%s", s + 1), n = strlen(s + 1);
    init_SA(), init_height();
    for (int i = 1; i <= n; i++) printf("%d ", sa[i]); puts("");
    for (int i = 1; i <= n; i++) printf("%d ", ht[i]); puts("");
    return 0;
}