记录编号	382497	评测结果	AAAAAAATTT
题目名称	后缀排序	最终得分	70
用户昵称	CiGam	是否通过	未通过
代码语言	C++	运行时间	1.148 s
提交时间	2017-03-13 21:36:40	内存使用	13.87 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1050000;
int sa[maxn],t1[maxn],t2[maxn],c[maxn],n;
char s[maxn];
void build_sa(int m)
{
	int *x=t1,*y=t2;
	for(int i=0;i<m;i++) c[i]=0;
	for(int i=0;i<n;i++) c[x[i]=s[i]]++;
	for(int i=0;i<m;i++) c[i]+=c[i-1];
	for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
	for(int k=1;k<=n;k<<=1)
	{
		int p=0;
		for(int i=n-k;i<n;i++) y[p++]=i;
		for(int i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
		for(int i=0;i<m;i++) c[i]=0;
		for(int i=0;i<n;i++) c[x[y[i]]]++;
		for(int i=0;i<m;i++) c[i]+=c[i-1];
		for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
		swap(x,y);
		p=1,x[sa[0]]=0;
		for(int i=1;i<n;i++) x[sa[i]]= y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k] ? p-1 : p++;
		if(p>=n) break;
		m=p;
	}
} 
int main()
{
	freopen("sais.in","r",stdin);
	freopen("sais.out","w",stdout);
	scanf("%s",s);
	n=strlen(s);
	build_sa(256);
	for(int i=0;i<n;i++) printf("%d ",sa[i]);
	return 0;
}