代码

#include <cstdio>
#include <iostream>

typedef unsigned int uint;

const size_t _O_Buffer_Size(1 << 24);
char _O_Buffer[_O_Buffer_Size];
char* _O_pos(_O_Buffer);

inline bool is_alpha(const char& ch)
{
	return 'a' <= ch && ch <= 'z';
}

inline void putint(int x)
{
	if (x)
	{
		char _buf[9];
		char* _pos(_buf);
		do
			*_pos++ = x % 10 | '0';
		while (x /= 10);
		while (_pos-- != _buf)
			*_O_pos++ = *_pos;
	}
	else
		*_O_pos++ = '0';
}

const size_t _M_Size(1 << 24);
char _M[_M_Size];
char* _M_pos(_M);

void* operator new(size_t size)
{
	void* _pos(_M_pos);
	_M_pos += size;
	return _pos;
}

void operator delete(void* ptr) noexcept
{
}

// --------------------------------------------------

using namespace std;

const size_t Size(100005);

// 后缀类型
const bool S_type(true);	// smaller
const bool L_type(false);	// larger

// 判断是否为LMS类型 
inline bool is_LMS_type(bool type[], int x)
{
	return x && type[x - 1] == L_type && type[x] == S_type;
}

// 判断两个LMS子串是否相同
inline bool equal_substring(int S[], int x, int y, bool type[])
{
	do
		if (S[x++] != S[y++])
			return false;
	while (!is_LMS_type(type, x) && !is_LMS_type(type, y));
	return S[x] == S[y];
}

// 诱导排序(从*型诱导到L型、从L型诱导到S型)
// 调用之前应将*型按要求放入SA中
inline void induced_sort(int S[], int SA[], bool type[], int bucket[], int lbucket[], int sbucket[], const int& length, const int& Sigma_Size)
{
	for (int i(1); i <= Sigma_Size; ++i)  // Reset S-type bucket
		sbucket[i] = bucket[i] - 1;
	
	for (int i(0); i <= length; ++i)
		if (SA[i] > 0 && type[SA[i] - 1] == L_type)
			SA[lbucket[S[SA[i] - 1]]++] = SA[i] - 1;
	for (int i(length); ~i; --i)
		if (SA[i] > 0 && type[SA[i] - 1] == S_type)
			SA[sbucket[S[SA[i] - 1]]--] = SA[i] - 1;
}

// SA-IS主体
// S是输入字符串，length是字符串的长度, SIGMA是字符集的大小
int* SAIS(int S[], const int& length, const int& Sigma_Size)
{
	bool* type(new bool[length + 1]);	// 后缀类型
	int* position(new int[length + 1]);	// 记录LMS子串的起始位置
	int* name(new int[length + 1]);		// 记录每个LMS子串的新名称
	int* SA(new int[length + 1]);		// SA数组
	int* bucket(new int[Sigma_Size + 1]);	// 每个字符的桶
	int* lbucket(new int[Sigma_Size + 1]);	// 每个字符的L型桶的起始位置
	int* sbucket(new int[Sigma_Size + 1]);	// 每个字符的S型桶的起始位置
	
	// 确定后缀类型(利用引理2.1)
	type[length] = S_type;
	for (int i(length - 1); ~i; --i)
		if (S[i] == S[i + 1])
			type[i] = type[i + 1];
		else
			type[i] = S[i] < S[i + 1] ? S_type : L_type;
	
	// 寻找每个LMS子串
	int cnt(0);
	for (int i(1); i <= length; ++i)
		if (is_LMS_type(type, i))
			position[cnt++] = i;
	
	// 初始化每个桶
	for (int i(0); i <= length; ++i)
		++bucket[S[i]];
	lbucket[0] = sbucket[0] = 0;
	for (int i(1); i <= Sigma_Size; ++i)
	{
		bucket[i] += bucket[i - 1];
		lbucket[i] = bucket[i - 1];
		sbucket[i] = bucket[i] - 1;
	}
	
	// 对LMS子串进行排序
	fill(SA, SA + length + 1, -1);
	for (int i(0); i != cnt; ++i)
		SA[sbucket[S[position[i]]]--] = position[i];
	induced_sort(S, SA, type, bucket, lbucket, sbucket, length, Sigma_Size);
	
	// 为每个LMS子串命名
	fill(name, name + length + 1, -1);
	int lastx(-1), namecnt(1);	// 上一次处理的LMS子串与名称的计数
	bool multiple(false);
	for (int i(1); i <= length; ++i)
	{
		const int& x(SA[i]);
		if (is_LMS_type(type, x))
		{
			if (~lastx)
			{
				if (!equal_substring(S, x, lastx, type))
					++namecnt;
				else
					multiple = true;
			}
			name[x] = namecnt;
			lastx = x;
		}
	}
	name[length] = 0;
	
	// 生成S1
	int* S1(new int[cnt]);
	int pos(0);
	for (int i(0); i <= length; ++i)
		if (~name[i])
			S1[pos++] = name[i];
	
	int* SA1;
	if (!multiple)
	{
		SA1 = new int[cnt];		// 直接计算SA1
		for (int i(0); i != cnt; ++i)
			SA1[S1[i]] = i;
	}
	else
		SA1 = SAIS(S1, cnt - 1, namecnt);	// 递归计算SA1
	
	// 从SA1诱导到SA
	lbucket[0] = sbucket[0] = 0;
	for (int i(1); i <= Sigma_Size; ++i)
	{
		lbucket[i] = bucket[i - 1];
		sbucket[i] = bucket[i] - 1;
	}
	fill(SA, SA + length + 1, -1);
	for (int i(cnt - 1); ~i; --i)  // 这里是逆序扫描SA1，因为SA中S型桶是倒序的
		SA[sbucket[S[position[SA1[i]]]]--] = position[SA1[i]];
	induced_sort(S, SA, type, bucket, lbucket, sbucket, length, Sigma_Size);
	
	return SA;
}

int length(0);
char Buf[Size];
int S[Size];
int Rank[Size];
int LCP[Size];

inline void compute_LCP(int length, int SA[])
{
	int j(0);
	for (int i(0); i <= length; ++i)
		if (Rank[i])
		{
			if (j)
				--j;
			while (S[SA[Rank[i]] + j] == S[SA[Rank[i] - 1] + j])
				++j;
			LCP[Rank[i]] = j;
		}
}

int main(int argc, char** argv)
{
	std::fread(Buf, 1, Size, stdin);
	
	for (; is_alpha(Buf[length]); ++length)
		S[length] = Buf[length];
	
	int* SA(SAIS(S, length, 256));
	
	for (int i(1); i <= length; ++i)
		putint(SA[i] + 1), *_O_pos++ = ' ';
	*_O_pos++ = '\n';
	
	for (int i(0); i <= length; ++i)
		Rank[SA[i]] = i;
	
	compute_LCP(length, SA);
	
	for (int i(2); i <= length; ++i)
		putint(LCP[i]), *_O_pos++ = ' ';
	
	std::fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout);
	
	return 0;
}

评测结果