代码

#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)
#define DC int T = gi <int> (); while (T--)

using namespace std;

typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;

template <typename T>
inline T gi()
{
	T f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

const int INF = 0x3f3f3f3f, N = 1000003, M = N << 1;

char s[N];
int m, n, h, p, sa[N], rk[N], cnt[N], id[N], px[N], oldrk[M], ht[N];

inline bool cmp(int x, int y) {return oldrk[x] == oldrk[y] && oldrk[x + h] == oldrk[y + h];}

int main()
{
	//File("");
	scanf("%s", s + 1); n = strlen(s + 1);
	m = 300;
	for (int i = 1; i <= m; i+=1) cnt[i] = 0;
	for (int i = 1; i <= n; i+=1) ++cnt[rk[i] = s[i]];
	for (int i = 1; i <= m; i+=1) cnt[i] += cnt[i - 1];
	for (int i = n; i >= 1; i-=1) sa[cnt[rk[i]]--] = i;
	for (h = 1, p = 0; h < n; h <<= 1, m = p)
	{
		p = 0;
		for (int i = n; i > n - h; i-=1) id[++p] = i;
		for (int i = 1; i <= n; i+=1) if (sa[i] > h) id[++p] = sa[i] - h;
		for (int i = 1; i <= m; i+=1) cnt[i] = 0;
		for (int i = 1; i <= n; i+=1) ++cnt[px[i] = rk[id[i]]];
		for (int i = 1; i <= m; i+=1) cnt[i] += cnt[i - 1];
		for (int i = n; i >= 1; i-=1) sa[cnt[px[i]]--] = id[i];
		for (int i = 1; i <= n; i+=1) oldrk[i] = rk[i];
		p = 0;
		for (int i = 1; i <= n; i+=1) if (cmp(sa[i], sa[i - 1])) rk[sa[i]] = p; else rk[sa[i]] = ++p;
	}
	for (int i = 1; i <= n; i+=1) printf("%d ", sa[i]); puts("");
	for (int i = 1, k = 0; i <= n; i+=1)
	{
		if (k) --k;
		while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
		ht[rk[i]] = k;
	}
	for (int i = 2; i <= n; i+=1) printf("%d ", ht[i]);
	return 0;
}

评测结果