代码

#include<bits/stdc++.h>
using namespace std;

int get() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

const int N = 1e6 + 5;
int n, m;
char s[N];
int sa[N], rk[N], ht[N], cnt[N], id[N], p;

void GetSA() {
	m = 300;
	for(int i = 1; i <= n; i++) ++cnt[rk[i] = s[i]];
	for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
	for(int i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;
	for(int w = 1; w < n && p < n; w <<= 1, m = p) {
		p = 0;
		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;
		for(int i = 1; i <= m; i++) cnt[i] = 0;
		for(int i = 1; i <= n; i++) ++cnt[rk[i]];
		for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
		for(int i = n; i >= 1; i--) sa[cnt[rk[id[i]]]--] = id[i], id[i] = 0;
		swap(id, rk), rk[sa[1]] = p = 1;
		for(int i = 2; i <= n; i++)
			rk[sa[i]] = (id[sa[i]] == id[sa[i - 1]] && id[sa[i] + w] == id[sa[i - 1] + w])? p : ++p;
	}
}

void GetHeight() {
	for(int i = 1, k = 0; i <= n; i++) {
		if(k) --k;
		while(s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
		ht[rk[i]] = k;
	}
}

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

评测结果