代码

#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;
const int MAXN = 1e5 + 7;

inline int R()
{
    char ch = getchar();
    int rt = 0;
    bool isn = false;
    for ( ; ch > '9' || ch < '0'; ch = getchar() )
        isn = ch == '-' ? true : isn;
    for ( ; ch <= '9' && ch >= '0'; ch = getchar() )
        rt = rt * 10 + ch - '0';
    return isn ? -rt : rt;
}

char c[MAXN];
int rk[MAXN << 1], t[MAXN << 1], sa[MAXN];
int f[MAXN], o[MAXN], h[MAXN], ht[MAXN];

int main ()
{
	int ns = 0;
	scanf ( "%s", c );
	int l = strlen ( c );
	if ( l == 1 )
	{
		puts ( "1" );
		return 0;
	}
	for ( int i = 0; i < l; ++i )
		rk[i + 1] = c[i], ns = max ( ns, rk[i + 1] );
	for ( int nl = 1; nl < l; nl <<= 1, ns = l )
	{
		memset ( f, 0, sizeof f );
		for ( int i = 1; i <= l; ++i )
			++f[rk[i + nl]];
		for ( int i = 1; i <= ns; ++i )
			f[i] += f[i - 1];
		for ( int i = 1; i <= l; ++i )
			o[f[rk[i + nl]]--] = i;
		memset ( f, 0, sizeof f );
		for ( int i = 1; i <= l; ++i )
			++f[rk[i]];
		for ( int i = 1; i <= ns; ++i )
			f[i] += f[i - 1];
		for ( int i = l; i; --i )
			t[o[i]] = f[rk[o[i]]]--;
		for ( int i = 1; i <= l; ++i )
			sa[t[i]] = i;
		bool uq = false;
		for ( int i = 2; i <= l; ++i )
			if ( rk[sa[i]] == rk[sa[i - 1]] && rk[sa[i] + nl] == rk[sa[i - 1] + nl] )
				t[sa[i]] = t[sa[i - 1]], uq = true;
		swap ( t, rk );
		if ( !uq )
			break;
	}
	for ( int i = 1; i <= l; ++i )
		sa[rk[i]] = i;
	for ( int i = 1; i <= l; ++i )
		printf ( "%d ", sa[i] );
	puts ( "" );
	for ( int i = 1; i <= l; ++i )
	{
		h[i] = max ( h[i - 1] - 1, 0 );
		for ( int j = i + h[i], k = sa[rk[i] - 1] + h[i]; c[j - 1] == c[k - 1]; ++j, ++k )
			++h[i];
	}
	for ( int i = 2; i <= l; ++i )
		printf ( "%d ", h[sa[i]] );
	puts ( "" );
	return 0;
}

评测结果