代码

#pragma GCC optimize("Ofast", "unroll-loops", "omit-frame-pointer", "inline", "-ftree-vectorize", "-fopt-info-vec-all")
#pragma GCC option("arch=native", "tune=native", "no-zero-upper")
#pragma GCC target("sse,sse2,sse3,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define rint register int
namespace IO {
	char out[500005],*pout=out,*eout=out+500000;
	inline void flush() { fwrite(out,1,pout-out,stdout),pout=out; }
	inline void pc(char c) { pout==eout&&(fwrite(out,1,500000,stdout),pout=out); (*pout++)=c; }
	inline void put(int x) {
		static char stk[10];int top=0;
		while(x) stk[top++]=x%10,x/=10; !top?pc('0'),0:0; while(top--) pc(stk[top]+'0');
		pc(' ');
	}
}
using IO::put;
int s[(MAXN<<1)+5],SA[MAXN+5],Rank[MAXN+5],c[MAXN+5],p[MAXN+5],tmp[MAXN+5],n,m,hei[MAXN];
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++]]);\
	for(rint i=2;i<=m;i++) c[i]+=c[i-1]; memcpy(p+1,c+1,m<<2); for(rint i=n1;i;Ar(s1[i],--),i--);\
	for(rint i=1;i<=m;i++) p[i]=c[i-1]+1; 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);
}
int main(){
	scanf("%s",str+1); n=strlen(str+1); for(rint i=1;i<=n;i++) s[i]=str[i]-'a'+2;
	s[++n]=1; SAIS(s,t,tmp,n,27); --n; for(rint i=1;i<=n;i++) SA[i]=SA[i+1],Rank[SA[i]]=i;
	for(rint i=1,k=0;i<=n;hei[Rank[i]]=k,i++,k&&--k) for(rint j=SA[Rank[i]-1];s[i+k]==s[j+k];k++);
	for(rint i=1;i<=n;i++) put(SA[i]); IO::pc('\n'); for(rint i=2;i<=n;i++) put(hei[i]); IO::pc('\n'); IO::flush();
}

评测结果