先挂个代码和博客吧
blog
#include<bits/stdc++.h>
using namespace std;
#define ri register int
#define gc getchar
template<class T>void in(T &x)
{
x = 0; bool f = 0; char c = gc();
while (c < '0' || c > '9') {if (c == '-') f = 1; c = gc();}
while ('0' <= c && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = gc();}
if (f) x = -x;
}
#undef gc
#define N 1000010
char s[N];
int n, m;
// 字符串长度，桶的大小
int sa[N], rk[N];
// SA:排名为i的后缀的位置
// rank:位置为i的后缀的排名
int tp[N], tax[N];
// tp:第二关键字的排名为i的后缀的位置，
// 还被用作rank的暂存
// tax:每个排名对应的后缀数量，用作桶
void rsort() { // 基数排序
for (ri i = 1; i <= m; ++i) tax[i] = 0;
for (ri i = 1; i <= n; ++i) ++tax[rk[i]];
// 第i个桶的内容：第一关键字为第i的数量
// 我们枚举每个位置的第一关键字排名（rk[i]），添加到桶中
for (ri i = 1; i <= m; ++i) tax[i] += tax[i - 1];
// 为了计算方便，我们求出前缀和
// 注意这里是循环到M
for (ri i = n; i >= 1; --i) sa[tax[rk[tp[i]]]--] = tp[i];
// 解释一下：因为第一关键字可能对应很多第二关键字
// 我们要在第一关键字相同的情况下排第二关键字
// 为了方便，我们倒序枚举所有的第二关键字，这样它一定是所在桶的最后一名
// 根据我们就求出的前缀和，它就是所有后缀的第tax[rk[tp[i]]]名
// （（第二关键字排名为i的后缀的位置）的桶编号）的前缀和排名
// 因为我们取出了一个元素，所以这个桶的size要-1
// 这样，这个排名的后缀的位置就是tp[i]
}
void ssort() {
for (ri i = 1; i <= n; ++i) rk[i] = s[i], tp[i] = i;
// 初始时，每个字符的排名就是ASCII码
// 第二关键字就随便给个i
rsort();
// 计算出长度为1的SA和rk
for (ri w = 1, p = 0; p < n && w <= n; m = p, w <<= 1) {
// m = p : 改变桶的大小为排名的数量，当数量为N时，完成区分排名
// w是要求出的后缀的长度
p = 0; // p是计数器，记录有多少个后缀的排名不同
for (ri i = n - w + 1; i <= n; ++i) tp[++p] = i;
// 对于起始位置在[n-w+1,n]的后缀，它们没有第二关键字，所以他们的第二关键字最小
for (ri i = 1; i <= n; ++i)
if (sa[i] > w) tp[++p] = sa[i] - w;
// IMPORTANT
// 枚举每一个排名，看看它距离字符串开头是否>w，这样，这个位置就是一个后缀的第二关键字
// 因为我们要在每一个后缀前接上长度为w的后缀，所以tp[++p] = sa[i] - w;
// 注意，编号越小表示这个后缀的起始位置越靠前
// 我们的第二关键字要从小到大，而我们正好是按照从小到大的顺序枚举每一个后缀
rsort(); // 再来一遍
swap(rk, tp); // WARN swap rank & tp
// 我们已经更新了SA，我们还要更新rk，此时tp已经无用，直接备份上一个rk
rk[sa[1]] = p = 1; // 排名第一的后缀直接加入
for (ri i = 2; i <= n; ++i)
rk[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w])
? p : ++p;
// 这里的条件是指：它的第一关键字和第二关键字是否都和前一个相同，如果是，它和上一个并列
// 如果不是，它的排名要+1
// 检查一下p==n，break;（我们已经区分出所有后缀）
}
}
signed main() {
scanf("%s", s + 1);
n = strlen(s + 1);
m = 127; // 初始桶的大小，因为char最大就是127
ssort();
for (ri i = 1; i <= n; ++i) printf("%d ", sa[i]);
return 0;
}