代码

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e6 + 5;
char s[N];
int n, sa[N], rk[N], ork[N], buc[N], id[N], ht[N];
void build() {
	int m = 1 << 7, p = 0;
	for(int i = 1; i <= n; i++) buc[rk[i] = s[i]]++;
	for(int i = 1; i <= m; i++) buc[i] += buc[i - 1];
	for(int i = n; i; i--) sa[buc[rk[i]]--] = i;
	for(int w = 1; ; m = p, p = 0, w <<= 1) { // m 表示桶的大小, 等于上一轮的 rk 最大值.
		for(int i = n - w + 1; i <= n; i++) id[++p] = i; // 循环顺序无关, 顺序倒序都可以, 不影响最终结果.
		for(int i = 1; i <= n; i++) if(sa[i] > w) id[++p] = sa[i] - w;
		memset(buc, 0, m + 1 << 2); // 注意清空桶.
		memcpy(ork, rk, n + 1 << 2); // 注意拷贝 rk -> ork.
		p = 0;
		for(int i = 1; i <= n; i++) buc[rk[i]]++;
		for(int i = 1; i <= m; i++) buc[i] += buc[i - 1];
		for(int i = n; i; i--) sa[buc[rk[id[i]]]--] = id[i]; // 注意, 倒序枚举保证计数排序的稳定性. 基数排序的正确性基于内层计数排序的稳定性.
		for(int i = 1; i <= n; i++) rk[sa[i]] = ork[sa[i - 1]] == ork[sa[i]] && ork[sa[i - 1] + w] == ork[sa[i] + w] ? p : ++p; // 原排名二元组相同则新排名相同, 否则排名 +1.
		if(p == n) break; // n 个排名互不相同, 排序完成.
	}
}
int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	build();
	for(int i = 1; i <= n; i++) printf("%d ", sa[i]);
	puts("");
	for(int i = 1, k = 0; i <= n; i++) {
		if(k) k--;
		while(s[i + k] == s[sa[rk[i] - 1] + k]) k++; // sa[rk[i]] = i, 需要保证 s[0] 和 s[n + 1] 为空字符 (多测清空), 否则可能出错.
		ht[rk[i]] = k;
	}
	for(int i = 2; i <= n; i++) printf("%d ", ht[i]);
	puts("");
	return 0;
}

评测结果