代码

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define rint register int
#define gc() getchar()
inline int rf(int a=0,int s=0,int c=gc()){for(;c<48||c>57;s=c,c=gc());for(;c>47&&c<58;(a*=10)+=c-48,c=gc());return s^'-'?a:-a;}
#define BUF_SIZE 1000000
#define _END fwrite(_Ob,1,_O-_Ob,stdout), _O = _Ob
#define oc(a) (*_O++ = a)
char _Ob[BUF_SIZE+5], *_O = _Ob, _Os[25], *_Ot;
inline void os(string s){_O += s.copy(_O,s.length(),0), _O-_Ob >= BUF_SIZE-50 ? _END : 0;}
template <typename T> inline void oi(T x)
{
	if(!x){oc('0'); return;} if(x < 0) oc('-'), x = -x;
	for(_Ot = _Os; x; *_Ot++ = x%10+'0', x /= 10);
	for(; _Ot != _Os; oc(*--_Ot)); _O-_Ob >= BUF_SIZE-50 ? _END : 0;
}
int SA[MAXN+5], Rank[MAXN+5], Height[MAXN+5], n; char s[MAXN+5];
#define Radix(rk,ps) for(memset(book+1,0,m<<2), i = 1; i <= n; ++book[rk], i++);\
for(i = 1; i <= m; book[i] += book[i-1], i++); for(i = n; i; SA[book[Rank[ps]]--] = ps, i--);
void Doubling(rint i=0)
{
	static int book[MAXN+5], x[MAXN+5], m, p, L; m = 27; Radix(Rank[i]=s[i]-'a'+1,i);
	for(p = L = 1; p < n; m = p, L <<= 1)
	{
		for(p = 0, i = n-L+1; i <= n; x[++p] = i++); for(i = 1; i <= n; SA[i]>L?x[++p]=SA[i]-L:0, i++); Radix(Rank[x[i]],x[i]);
		for(memcpy(x+1,Rank+1,n<<2), Rank[SA[1]] = p = 1, i = 2; i <= n; Rank[SA[i]] = p+=x[SA[i]]^x[SA[~-i]]||x[SA[i]+L]^x[SA[~-i]+L], i++);
	}
}
void CalHeight(){for(rint i = 1, L = 0, j; i <= n; Height[Rank[i++]] = L) for(j = SA[~-Rank[i]], L-=L>0; i+L<=n&&j+L<=n&&s[i+L]==s[j+L]; ++L);}
int main()
{
	scanf("%s",s+1), n = strlen(s+1), Doubling(), CalHeight();
	for(rint i = 1; i <= n; oi(SA[i]), oc(' '), i++); oc('\n');
	for(rint i = 2; i <= n; oi(Height[i]), oc(' '), i++); oc('\n'); _END; return 0;
}

评测结果