记录编号	382438	评测结果	AAAAAAAAAA
题目名称	后缀排序	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.473 s
提交时间	2017-03-13 20:31:01	内存使用	10.16 MiB

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define int unsigned
const int maxn=1000005u;
int sa[maxn],wa[maxn],wb[maxn],cnt[maxn];char s[maxn],st[maxn<<2];
void Rabit_sa(register int n,register int m){
	register int *x=wa,*y=wb,*t;register int i,j,p;
	for(i=0;i<n;i++)cnt[x[i]=s[i]]++;
	for(i=1;i<m;i++)cnt[i]+=cnt[i-1];
	for(i=n-1;~i;i--)sa[--cnt[x[i]]]=i;
	for(i=0;i<m;i++)cnt[i]=0;
	for(j=1,p=1;p<n;m=p,j<<=1){
		for(p=0,i=n-j;i<n;i++)y[p++]=i;
		for(i=0;i<n;i++){cnt[i]=0;if(sa[i]>=j)y[p++]=sa[i]-j;}
		for(i=0;i<n;i++)cnt[x[y[i]]]++;
		for(i=1;i<m;i++)cnt[i]+=cnt[i-1];
		for(i=n-1;~i;i--)sa[--cnt[x[y[i]]]]=y[i];
		for(t=x,x=y,y=t,p=1,i=1,x[sa[0]]=0;i<n;i++)
			x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j])?p-1:p++;
	}
}
bool Main(),MAIN=Main();signed main(){;}
bool Main(){
	freopen("sais.in","r",stdin);freopen("sais.out","w",stdout);
	register int i,n=0,m;
	do s[n++]=getchar();while(s[n-1]>'!');s[--n]=0;
	Rabit_sa(n+1,200);m=0;
	for(i=n;i;i--){		
		if(!sa[i])st[m++]='0';
		while(sa[i])st[m++]=sa[i]%10+48,sa[i]/=10;st[m++]=' ';
	}m--;
	while(~m)putchar(st[m--]);putchar('\n');
}