文件详细信息

下载本文件

本文件的大小为 1005 字节。

//Luogu P3809 / LOJ 111
#include<algorithm>
#include<cstdio>
#include<cstring>
const int maxn=1000005;
char s[maxn];
int n,m,sa[maxn],rk[maxn<<1],oldrk[maxn<<1],id[maxn],cnt[maxn];
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	m=n>130?n:130;
	for(int i=1;i<=n;i++)++cnt[rk[i]=s[i]];
	for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;i--)sa[cnt[rk[i]]--]=i;
	for(int w=1;w<n;w<<=1){
		memset(cnt,0,sizeof(int)*(m+1));
		for(int i=1;i<=n;i++)++cnt[rk[(id[i]=sa[i])+w]];
		for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--)sa[cnt[rk[id[i]+w]]--]=id[i];
		memset(cnt,0,sizeof(int)*(m+1));
		for(int i=1;i<=n;i++)++cnt[rk[id[i]=sa[i]]];
		for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--)sa[cnt[rk[id[i]]]--]=id[i];
		memcpy(oldrk,rk,sizeof(int)*(n+1));
		int p=0;
		for(int i=1;i<=n;i++)
			if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w])rk[sa[i]]=p;
			else rk[sa[i]]=++p;
		m=p;
		if(p==n)break;
	}
	for(int i=1;i<=n;i++)printf("%d ",sa[i]);
	return 0;
}