代码

#include <cstdio>
#include <cstring>

#include <algorithm>

using namespace std;

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

const int N = 100010;

int n;
char s[N];
int rk[N], sa[N], ht[N], cnt[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 t = 1; t < n; t <<= 1) {
		memset(cnt, 0, sizeof(cnt));
		for (int i = 1; i <= n; ++i) {
			p[i].id = i;
			p[i].a = rk[i];
			p[i].b = (i + t > n) ? 0 : rk[i + t];
		}
		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];
		int c = 0;
		for (int i = 1; i <= n; ++i) {
			if (p[i].a != p[i - 1].a || p[i].b != p[i - 1].b)
				++c;
			rk[p[i].id] = c;
		}
		if (c == n)
			break;
	}
	for (int i = 1; i <= n; ++i)
		sa[rk[i]] = i;
	int h = 0;
	for (int i = 1; i <= n; ++i) {
		h = max(h - 1, 0);
		while (s[i + h] == s[sa[rk[i] + 1] + h])
			++h;
		ht[rk[i]] = h;
	}
	for (int i = 1; i <= n; ++i)
		printf("%d ", sa[i]);
	putchar('\n');
	for (int i = 1; i < n; ++i)
		printf("%d ", ht[i]);
	return 0;
}

评测结果