代码

#include <cstdio>
#include <algorithm>
#include <numeric>
#include <cstring>

struct IO_Tp
{
	const static int _O_Buffer_Size = 2 << 20;
	char _O_Buffer[_O_Buffer_Size], *_O_pos = _O_Buffer;
	
	~IO_Tp() { fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout); }
	
	IO_Tp &operator<<(int n)
	{
		static char _buf[10];
		char* _pos = _buf;
		do
			*_pos++ = '0' + n % 10;
		while (n /= 10);
		while (_pos != _buf)
			*_O_pos++ = *--_pos;
		return *this;
	}
	
	IO_Tp &operator<<(char ch)
	{
		*_O_pos++ = ch;
		return *this;
	}
} IO;

const int Max_N = 100005;

namespace SA_IS
{
	int *sa, cnt[Max_N], cur[Max_N];
	
	template<typename _Char>
	inline void push_S(const _Char s[], const int x) { sa[--cur[s[x]]] = x; }
	template<typename _Char>
	inline void push_L(const _Char s[], const int x) { sa[cur[s[x]]++] = x; }
	
	template<typename _Char>
	inline void induced_sort(const int n, const int m, const int n1, const _Char s[], const char type[], const int v[])
	{
		std::fill(sa, sa + n, -1);
		std::fill(cnt, cnt + m, 0);
		for (int i = 0; i < n; ++i)
			++cnt[s[i]];
		std::partial_sum(cnt, cnt + m, cnt);
		
		std::copy(cnt, cnt + m, cur);
		for (int i = n1 - 1; ~i; --i)
			push_S(s, v[i]);
		
		std::copy(cnt, cnt + m - 1, cur + 1);
		for (int i = 0; i < n; ++i)
			if (sa[i] > 0 && type[sa[i] - 1] == 0)
				push_L(s, sa[i] - 1);
		
		std::copy(cnt, cnt + m, cur);
		for (int i = n - 1; ~i; --i)
			if (sa[i] > 0 && type[sa[i] - 1])
				push_S(s, sa[i] - 1);
	}
	
	template<typename _Char>
	inline bool lms_equal(_Char s[], char type[], int x, int y)
	{
		if (s[x] == s[y])
			while (s[++x] == s[++y])
				if (type[x] == 2 || type[y] == 2)
					return false;
		return true;
	}
	
	template<typename _Char>
	void sais_core(const int n, const int m, _Char s[], char type[], int lms[])
	{
		int n1 = 0, ch = -1;
		
		type[n - 1] = 1;
		for (int i = n - 2; ~i; --i)
			type[i] = s[i] == s[i + 1] ? type[i + 1] : s[i] < s[i + 1];
		
		for (int i = 1; i < n; ++i)
			if (type[i - 1] == 0 && type[i] == 1)
				type[i] = 2, lms[n1++] = i;
		induced_sort(n, m, n1, s, type, lms);
		
		n1 = 0;
		for (int i = 0; i < n; ++i)
			if (type[sa[i]] == 2)
				sa[n1++] = sa[i];
		std::fill(sa + n1, sa + n, -1);
		int *s1 = sa + n1;
		for (int i = 0; i < n1; ++i)
			if (type[sa[i]] == 2)
				s1[sa[i] >> 1] = ch += i == 0 || lms_equal(s, type, sa[i], sa[i - 1]);
		std::remove(s1, sa + n, -1);
		
		if (ch + 1 < n1)
			sais_core(n1, ch + 1, s1, type + n, lms + n1);
		else
			for (int i = 0; i < n1; ++i)
				sa[s1[i]] = i;
		
		for (int i = 0; i < n1; ++i)
			lms[n1 + i] = lms[sa[i]];
		induced_sort(n, m, n1, s, type, lms + n1);
	}
	
	template<typename _Char>
	void main(const _Char s[], const int n)
	{
		static _Char _s[Max_N];
		static int _lms[Max_N << 1];
		static char _type[Max_N << 1];
		int min = s[0], max = s[0];
		for (int i = 1; i < n; ++i)
			min = std::min<int>(min, s[i]), max = std::max<int>(max, s[i]);
		for (int i = 0; i < n; ++i)
			_s[i] = s[i] - min + 1;
		_s[n] = 0;
		sais_core(n + 1, max - min + 1 + 1, _s, _type, _lms);
	}
}

void klaap(const char s[], const int sa[], int lcp[], const int n)
{
	static int rk[Max_N];
	for (int i = 0; i < n; ++i)
		rk[sa[i]] = i;
	for (int i = 0, h = lcp[0] = 0; i < n; ++i)
		if (h -= h != 0, rk[i])
		{
			for (int j = sa[rk[i] - 1]; i + h < n && j + h < n && s[i + h] == s[j + h]; ++h)
				;
			lcp[rk[i]] = h;
		}
}

char s[Max_N];
int N;
int sa[Max_N], lcp[Max_N];

int main(int argc, char **argv)
{
	scanf("%s", s);
	N = strlen(s);
	
	SA_IS::sa = sa;
	SA_IS::main(s, N);
	klaap(s, sa + 1, lcp, N);
	
	for (int i = 1; i <= N; ++i)
		IO << sa[i] + 1 << " \n"[i == N];
	for (int i = 1; i < N; ++i)
		IO << lcp[i] << " \n"[i == N];
	
	return 0;
}

评测结果