代码

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

const int N = 1e5 + 10;

char buffer[N * 100], *buffer_ptr = buffer;
#define alloc(x, type, len) type* x = (type*)buffer_ptr; buffer_ptr += (len) * sizeof(type)

void induced_sort(int n, int m, int *s, bool *T, int *sa, int *cnt)
{
	static int lptr[N], rptr[N];
	int tmp;
	lptr[0] = rptr[0] = 0;
	for (int i = 1; i <= m; ++i) lptr[i] = cnt[i - 1], rptr[i] = cnt[i] - 1;
	for (int i = 0; i <= n; ++i) sa[i] > 0 && !T[tmp = sa[i] - 1] ? sa[lptr[s[tmp]]++] = tmp : 0;
	for (int i = n; i >= 0; --i) sa[i] > 0 &&  T[tmp = sa[i] - 1] ? sa[rptr[s[tmp]]--] = tmp : 0;
}

bool compare(int *x, int *y, int n)
{
	while (n--) if (*x++ != *y++) return 1;
	return 0;
}

void sais(int n, int m, int *s, int *sa)
{
	--n;
	alloc(T, bool, n + 10);
	alloc(cnt, int, m + 10);
	alloc(lms, int, n + 10);
	alloc(tmp, int, n + 10);

	for (int i = n; i >= 0; --i)
	{
		T[i] = (i == n || s[i] < s[i + 1] || s[i] == s[i + 1] && T[i + 1]);
		++cnt[s[i]];
	}
	tmp[0] = 0;
	for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1], tmp[i] = cnt[i] - 1;

	int LMS = 0;
	for (int i = 1; i <= n; ++i) T[i] && !T[i - 1] ? lms[LMS++] = i : 0;

	memset(sa, -1, (n + 1) << 2);
	for (int i = 0; i < LMS; ++i) sa[tmp[s[lms[i]]]--] = lms[i];
	induced_sort(n, m, s, T, sa, cnt);

	alloc(len, int, n + 10);
	lms[LMS] = n + 1;
	for (int i = 0; i < LMS; ++i) len[lms[i]] = lms[i + 1] - lms[i] + 1;
	alloc(lab, int, n + 10);
	int m0 = 0;
	memset(lab, -1, (n + 1) << 2);
	for (int i = 1, p = -1, q = -1; i <= n; ++i)
		if ((q = sa[i]) > 0 && T[q] && !T[q - 1])
		{
			if (p == -1 || len[p] != len[q] || compare(s + p, s + q, len[p])) ++m0;
			lab[q] = m0; p = q;
		}
	lab[n] = 0;

	alloc(s0, int, LMS + 10);
	alloc(sa0, int, LMS + 10);
	for (int i = 0, p = 0; i <= n; ++i) lab[i] >= 0 ? s0[p++] = lab[i] : 0;
	if (m0 + 1 == LMS) for (int i = 0; i < LMS; ++i) sa0[s0[i]] = i;
	else sais(LMS, m0, s0, sa0);

	tmp[0] = 0;
	for (int i = 1; i <= m; ++i) tmp[i] = cnt[i] - 1;
	memset(sa, -1, (n + 1) << 2);
	for (int i = LMS - 1; i >= 0; --i) sa[tmp[s[lms[sa0[i]]]]--] = lms[sa0[i]];
	induced_sort(n, m, s, T, sa, cnt);
}

char output_buffer[N * 20], *output_ptr = output_buffer;
void print(int v, char step = ' ')
{
	if (v)
	{
		static int str[20];
		int len = 0;
		for (; v; v /= 10) str[len++] = v % 10;
		while (len--) *output_ptr++ = str[len] + '0';
	}
	else *output_ptr++ = '0';
	*output_ptr++ = step;
}
void flush()
{
	fwrite(output_buffer, 1, output_ptr - output_buffer, stdout);
}

int main()
{
	alloc(str, char, N);
	fread(str, 1, N, stdin);
	int n = 0;
	while (isalpha(str[n])) ++n;
	alloc(s, int, n + 10);
	alloc(sa, int, n + 10);
	for (int i = 0; i < n; ++i) s[i] = str[i] - 'a' + 1;
	sais(n + 1, 26, s, sa);
	for (int i = 1; i <= n; ++i) print(sa[i] + 1, i == n ? '\n' : ' ');
	alloc(r, int, n + 10);
	alloc(h, int, n + 10);
	for (int i = 1; i <= n; ++i) r[sa[i]] = i;
	for (int k = 0, i = 0, j; i < n; h[r[i++]] = k)
	for (k ? k-- : 0, j = sa[r[i] - 1]; s[i + k] == s[j + k]; ++k);
	for (int i = 2; i <= n; ++i) print(h[i], i == n ? '\n' : ' ');
	flush();
	return 0;
}

评测结果