文件详细信息

下载本文件

本文件的大小为 595 字节。

//Luogu P3809 / LOJ 111
#include<algorithm>
#include<cstdio>
#include<cstring>
const int maxn=1000005;
char s[maxn];
int n,w,sa[maxn],rk[maxn<<1],oldrk[maxn<<1];
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++)sa[i]=i,rk[i]=s[i];
	for(w=1;w<n;w<<=1){
		std::sort(sa+1,sa+n+1,[](int x,int y){
			return rk[x]==rk[y]?rk[x+w]<rk[y+w]:rk[x]<rk[y];
		});
		memcpy(oldrk,rk,sizeof(oldrk));
		for(int i=1,p=0;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;
	}
	for(int i=1;i<=n;i++)printf("%d ",sa[i]);
	return 0;
}