代码

#include<bits/stdc++.h>
#define maxn 1000006
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)
using namespace std;

namespace SA{
	int sa[maxn],h[maxn],rk[maxn],s[maxn<<1],t[maxn<<1],p[maxn],c[maxn],l[maxn];
	#define pushS(x) sa[l[s[x]]--]=x
	#define pushL(x) sa[l[s[x]]++]=x
	#define _Sort(v) memset(sa,0,4*n),memset(c,0,4*m); 							 \
	rep(i,0,n-1) c[s[i]]++;rep(i,1,m-1) c[i]+=c[i-1];							 \
	rep(i,0,m-1) l[i]=c[i]-1;per(i,n1-1,0) pushS(v[i]);							 \
	rep(i,1,m-1) l[i]=c[i-1];rep(i,0,n-1) if(sa[i]&&t[sa[i]-1])pushL(sa[i]-1); \
	rep(i,0,m-1) l[i]=c[i]-1;per(i,n-1,0) if(sa[i]&&!t[sa[i]-1])pushS(sa[i]-1);
	void sais(int n,int m,int *s,int *t,int *p){
		int n1 = t[n-1] = 0 , ch = rk[0] = -1 , *s1 = s + n;
		per(i,n-2,0) t[i]=s[i]^s[i+1]?s[i]>s[i+1]:t[i+1];
		rep(i,0,n-1) rk[i]=t[i-1]&&!t[i]?p[n1]=i,n1++:-1;
		_Sort(p);
		for(int i=0,x,y;i<n;i++) if(~(x=rk[sa[i]])){
			if(ch<0||p[x+1]-p[x]^p[y+1]-p[y]) ch++;
			else for(int j=p[x],k=p[y];j<=p[x+1];j++,k++)
				if(s[j]^s[k]||t[j]^t[k]){ ch++;break; }
			s1[y=x]=ch;
		}
		if(ch+1<n1) sais(n1,ch+1,s1,t+n,p+n1);
		else rep(i,0,n1-1) sa[s1[i]]=i;
		rep(i,0,n1-1) s1[i]=p[sa[i]];
		_Sort(s1);
	}
	template<class T>void SA(int n,T *S){
		rep(i,0,n-1) s[i]=S[i];s[n++]=0;
		sais(n,130,s,t,p);
	}
}
char s[maxn];

namespace IO{
	char wb[1<<23],*ws=wb;
	template<class T>void put(T a,char s){
		static int q[30]={};
		if(!a) q[++q[0]]=0;
		for(;a;a/=10) q[++q[0]]=a%10;
		for(;q[0];) *(ws++)=q[q[0]--]+'0';
		*(ws++)=s;
	}
	void flush(){
		fwrite(wb,1,ws-wb,stdout);
	}
}

int main(){
	int n = fread(s,1,maxn,stdin);
	SA::SA(n,s);
	rep(i,1,n) IO::put(SA::sa[i]+1," \n"[i==n]);
	IO::flush();
}

评测结果