代码

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
#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 s[(MAXN<<1)+5], SA[MAXN+5], Rank[MAXN+5], Height[MAXN+5], c[MAXN+5], p[MAXN+5], tmp[MAXN+5], n, m; char str[MAXN+5]; bool t[(MAXN<<1)+5];
#define Ar(x,a) SA[p[s[x]]a]=x
#define IS(s1)\
	memset(SA+1,0,n<<2); memset(c+1,0,m<<2); for(rint i = 1; i <= n; ++c[s[i++]]);\
	partial_sum(c+1,c+m+1,c+1); memcpy(p+1,c+1,m<<2); for(rint i = n1; i; Ar(s1[i],--), i--);\
	transform(c,c+m,p+1,[](int a){return++a;}); for(rint i = 1; i <= n; SA[i]>1&&t[SA[i]-1]?Ar(SA[i]-1,++):0, i++);\
	memcpy(p+1,c+1,m<<2); for(rint i = n; i; SA[i]>1&&!t[SA[i]-1]?Ar(SA[i]-1,--):0, i--);
void SAIS(int s[], bool t[], int tmp[], int n, int m){
	int n1 = 0, m1 = Rank[1] = 0, *s1 = s+n; t[n] = 0;
	for(rint i = n-1; i; t[i] = s[i]^s[i+1]?s[i]>s[i+1]:t[i+1], i--);
	for(rint i = 2; i <= n; Rank[i] = t[i-1]&&!t[i]?tmp[++n1]=i,n1:0, i++); IS(tmp);
	for(rint i = 1, x, y = 0; i <= n; i++) if(x=Rank[SA[i]]){
		if(m1 <= 1 || tmp[x+1]-tmp[x]!=tmp[y+1]-tmp[y]) ++m1;
		else for(rint a = tmp[x], b = tmp[y]; a <= tmp[x+1]; a++, b++)
				if((s[a]<<1|t[a])^(s[b]<<1|t[b])){++m1; break;}
		s1[y=x] = m1;
	}
	if(m1 < n1) SAIS(s1,t+n,tmp+n1,n1,m1); else for(rint i = 1; i <= n1; SA[s1[i]] = i, i++);
	for(rint i = 1; i <= n1; s1[i] = tmp[SA[i]], i++); IS(s1);
}
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",str+1); n = strlen(str+1); for(rint i = 1; i <= n; s[i] = str[i]-'a'+2, i++);
	s[++n] = 1; SAIS(s,t,tmp,n,27); --n; for(rint i = 1; i <= n; Rank[SA[i]=SA[i+1]]=i, i++); 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;
}

评测结果