代码

#include<cstdio>
#include<cstring>
#include<iostream>

using iarrN = int[1000003];

char s[1000003];
int N, M;
iarrN c, rnk, sa, t, H;

void rSort() {
	static bool g = 0;
	g ? memset(c + 1, 0, sizeof(int) * M), 0 : g = 1;

	for (int i = 1; i <= N; ++i)
		++c[rnk[i]];
	for (int i = 2; i <= M; ++i)
		c[i] += c[i - 1];
	for (int i = N; i; --i)
		sa[c[rnk[t[i]]]--] = t[i];
}

void sufSort() {
	M = 'z' - '0' + 1; // 75
	for (int i = 1; i <= N; ++i)
		rnk[i] = s[i] - '0' + 1, t[i] = i;
	rSort();
	M = 0;
	for (int w = 1; M < N; w <<= 1) {
		M = 0;
		for (int i = N - w + 1; i <= N; ++i)
			t[++M] = i;
		for (int i = 1; i <= N; ++i)
			if (sa[i] > w) t[++M] = sa[i] - w;
		rSort();
		memcpy(t + 1, rnk + 1, N << 2);
		rnk[sa[1]] = M = 1;
		for (int i = 2; i <= N; ++i)
			rnk[sa[i]] = (t[sa[i - 1]] == t[sa[i]]
				&& t[sa[i - 1] + w] == t[sa[i] + w]) ? M : ++M;
	}
	for (int i = 1, j = 0; i <= N; ++i) {
		if (rnk[i] == 1) continue;
		while (s[i + j] == s[sa[rnk[i] - 1] + j])
			++j;
		H[rnk[i]] = j;
		if (j) --j;
	}
}

int main() {
	scanf("%s", s + 1);
	N = strlen(s + 1);
	sufSort();
	for (int i = 1; i <= N; ++i)
		std::cout << sa[i] << ' ';
	std::cout << '\n';
	for (int i = 2; i <= N; ++i)
		std::cout << H[i] << ' ';
	return 0;
}

评测结果