代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
const int UCHAR_SIZE=256;const int MINBUCKETSIZE=256;typedef int sais_index_type;typedef int sais_bool_type;const int SAIS_LMSSORT2_LIMIT=0x3fffffff;void getCounts(const void*T,sais_index_type*C,sais_index_type n,sais_index_type k,int cs){sais_index_type i;for(i=0;i<k;++i)C[i]=0;for(i=0;i<n;++i)++C[(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(i)]:((unsigned char*)T)[(i)])];}void getBuckets(const sais_index_type*C,sais_index_type*B,sais_index_type k,sais_bool_type end){sais_index_type i,sum=0;if(end)for(i=0;i<k;++i){sum+=C[i];B[i]=sum;}else for(i=0;i<k;++i){sum+=C[i];B[i]=sum-C[i];}}void LMSsort1(const void*T,sais_index_type*SA,sais_index_type*C,sais_index_type*B,sais_index_type n,sais_index_type k,int cs){sais_index_type*b,i,j;sais_index_type c0,c1;if(C==B)getCounts(T,C,n,k,cs);getBuckets(C,B,k,0);j=n-1;b=SA+B[c1=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j)]:((unsigned char*)T)[(j)])];--j;*b++=((cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j)]:((unsigned char*)T)[(j)])<c1)?~j:j;for(i=0;i<n;++i){if(0<(j=SA[i])){if((c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j)]:((unsigned char*)T)[(j)]))!=c1){B[c1]=b-SA;b=SA+B[c1=c0];}--j;*b++=((cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j)]:((unsigned char*)T)[(j)])<c1)?~j:j;SA[i]=0;}else if(j<0)SA[i]=~j;}if(C==B)getCounts(T,C,n,k,cs);getBuckets(C,B,k,1);for(i=n-1,b=SA+B[c1=0];0<=i;--i){if(0<(j=SA[i])){if((c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j)]:((unsigned char*)T)[(j)]))!=c1){B[c1]=b-SA;b=SA+B[c1=c0];}--j;*--b=((cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j)]:((unsigned char*)T)[(j)])>c1)?~(j+1):j;SA[i]=0;}}}sais_index_type LMSpostproc1(const void*T,sais_index_type*SA,sais_index_type n,sais_index_type m,int cs){sais_index_type i,j,p,q,plen,qlen,name;sais_index_type c0,c1;sais_bool_type diff;for(i=0;(p=SA[i])<0;++i)SA[i]=~p;if(i<m){for(j=i,++i;;++i){if((p=SA[i])<0){SA[j++]=~p;SA[i]=0;if(j==m)break;}}}i=n-1;j=n-1;c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(n-1)]:((unsigned char*)T)[(n-1)]);do{c1=c0;}while((0<=--i)&&((c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(i)]:((unsigned char*)T)[(i)]))>=c1));for(;0<=i;){do{c1=c0;}while((0<=--i)&&((c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(i)]:((unsigned char*)T)[(i)]))<=c1));if(0<=i){SA[m+((i+1)>>1)]=j-i;j=i+1;do{c1=c0;}while((0<=--i)&&((c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(i)]:((unsigned char*)T)[(i)]))>=c1));}}for(i=0,name=0,q=n,qlen=0;i<m;++i){p=SA[i],plen=SA[m+(p>>1)],diff=1;if((plen==qlen)&&((q+plen)<n)){for(j=0;(j<plen)&&((cs==sizeof(sais_index_type)?((sais_index_type*)T)[(p+j)]:((unsigned char*)T)[(p+j)])==(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(q+j)]:((unsigned char*)T)[(q+j)]));++j);if(j==plen)diff=0;}if(diff!=0)++name,q=p,qlen=plen;SA[m+(p>>1)]=name;}return name;}void LMSsort2(const void*T,sais_index_type*SA,sais_index_type*C,sais_index_type*B,sais_index_type*D,sais_index_type n,sais_index_type k,int cs){sais_index_type*b,i,j,t,d;sais_index_type c0,c1;getBuckets(C,B,k,0);j=n-1;b=SA+B[c1=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j)]:((unsigned char*)T)[(j)])];--j;t=((cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j)]:((unsigned char*)T)[(j)])<c1);j+=n;*b++=(t&1)?~j:j;for(i=0,d=0;i<n;++i){if(0<(j=SA[i])){if(n<=j)d+=1,j-=n;if((c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j)]:((unsigned char*)T)[(j)]))!=c1){B[c1]=b-SA;b=SA+B[c1=c0];}--j;t=c0;t=(t<<1)|((cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j)]:((unsigned char*)T)[(j)])<c1);if(D[t]!=d)j+=n,D[t]=d;*b++=(t&1)?~j:j;SA[i]=0;}else if(j<0)SA[i]=~j;}for(i=n-1;0<=i;--i){if(0<SA[i]){if(SA[i]<n){SA[i]+=n;for(j=i-1;SA[j]<n;--j);SA[j]-=n;i=j;}}}getBuckets(C,B,k,1);for(i=n-1,d+=1,b=SA+B[c1=0];0<=i;--i){if(0<(j=SA[i])){if(n<=j)d+=1,j-=n;if((c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j)]:((unsigned char*)T)[(j)]))!=c1){B[c1]=b-SA;b=SA+B[c1=c0];}--j;t=c0;t=(t<<1)|((cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j)]:((unsigned char*)T)[(j)])>c1);if(D[t]!=d)j+=n,D[t]=d;*--b=(t&1)?~(j+1):j;SA[i]=0;}}}sais_index_type LMSpostproc2(sais_index_type*SA,sais_index_type n,sais_index_type m){sais_index_type i,j,d,name;for(i=0,name=0;(j=SA[i])<0;++i){j=~j;if(n<=j)name+=1;SA[i]=j;}if(i<m){for(d=i,++i;;++i){if((j=SA[i])<0){j=~j;if(n<=j)name+=1;SA[d++]=j;SA[i]=0;if(d==m)break;}}}if(name<m){for(i=m-1,d=name+1;0<=i;--i){if(n<=(j=SA[i]))j-=n,--d;SA[m+(j>>1)]=d;}}else{for(i=0;i<m;++i){if(n<=(j=SA[i]))j-=n,SA[i]=j;}}return name;}void induceSA(const void*T,sais_index_type*SA,sais_index_type*C,sais_index_type*B,sais_index_type n,sais_index_type k,int cs){sais_index_type*b,i,j;sais_index_type c0,c1;if(C==B)getCounts(T,C,n,k,cs);getBuckets(C,B,k,0);j=n-1;b=SA+B[c1=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j)]:((unsigned char*)T)[(j)])];*b++=((0<j)&&((cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j-1)]:((unsigned char*)T)[(j-1)])<c1))?~j:j;for(i=0;i<n;++i){j=SA[i],SA[i]=~j;if(0<j){--j;if((c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j)]:((unsigned char*)T)[(j)]))!=c1){B[c1]=b-SA;b=SA+B[c1=c0];}*b++=((0<j)&&((cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j-1)]:((unsigned char*)T)[(j-1)])<c1))?~j:j;}}if(C==B)getCounts(T,C,n,k,cs);getBuckets(C,B,k,1);for(i=n-1,b=SA+B[c1=0];0<=i;--i){if(0<(j=SA[i])){--j;if((c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j)]:((unsigned char*)T)[(j)]))!=c1){B[c1]=b-SA;b=SA+B[c1=c0];}*--b=((j==0)||((cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j-1)]:((unsigned char*)T)[(j-1)])>c1))?~j:j;}else SA[i]=~j;}}sais_index_type computeBWT(const void*T,sais_index_type*SA,sais_index_type*C,sais_index_type*B,sais_index_type n,sais_index_type k,int cs){sais_index_type*b,i,j,pidx=-1;sais_index_type c0,c1;if(C==B)getCounts(T,C,n,k,cs);getBuckets(C,B,k,0);j=n-1;b=SA+B[c1=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j)]:((unsigned char*)T)[(j)])];*b++=((0<j)&&((cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j-1)]:((unsigned char*)T)[(j-1)])<c1))?~j:j;for(i=0;i<n;++i){if(0<(j=SA[i])){--j;SA[i]=~((sais_index_type)(c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j)]:((unsigned char*)T)[(j)])));if(c0!=c1){B[c1]=b-SA;b=SA+B[c1=c0];}*b++=((0<j)&&((cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j-1)]:((unsigned char*)T)[(j-1)])<c1))?~j:j;}else if(j!=0)SA[i]=~j;}if(C==B)getCounts(T,C,n,k,cs);getBuckets(C,B,k,1);for(i=n-1,b=SA+B[c1=0];0<=i;--i){if(0<(j=SA[i])){--j;SA[i]=(c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j)]:((unsigned char*)T)[(j)]));if(c0!=c1){B[c1]=b-SA;b=SA+B[c1=c0];}*--b=((0<j)&&((cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j-1)]:((unsigned char*)T)[(j-1)])>c1))?~((sais_index_type)(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j-1)]:((unsigned char*)T)[(j-1)])):j;}else if(j!=0)SA[i]=~j;else pidx=i;}return pidx;}sais_index_type sais_main(const void*T,sais_index_type*SA,sais_index_type fs,sais_index_type n,sais_index_type k,int cs,sais_bool_type isbwt){sais_index_type*C,*B,*D,*RA,*b;sais_index_type i,j,m,p,q,t,name,pidx=0,newfs;sais_index_type c0,c1;unsigned int flags;if(k<=MINBUCKETSIZE){if((C=((sais_index_type*)malloc((k)*sizeof(sais_index_type))))==NULL)return-2;if(k<=fs){B=SA+(n+fs-k);flags=1;}else{if((B=((sais_index_type*)malloc((k)*sizeof(sais_index_type))))==NULL){free(C);return-2;}flags=3;}}else if(k<=fs){C=SA+(n+fs-k);if(k<=(fs-k)){B=C-k;flags=0;}else if(k<=(MINBUCKETSIZE*4)){if((B=((sais_index_type*)malloc((k)*sizeof(sais_index_type))))==NULL)return-2;flags=2;}else{B=C;flags=8;}}else{if((C=B=((sais_index_type*)malloc((k)*sizeof(sais_index_type))))==NULL)return-2;flags=4|8;}if((n<=SAIS_LMSSORT2_LIMIT)&&(2<=(n/k))){if(flags&1)flags|=((k*2)<=(fs-k))?32:16;else if((flags==0)&&((k*2)<=(fs-k*2)))flags|=32;}getCounts(T,C,n,k,cs);getBuckets(C,B,k,1);for(i=0;i<n;++i)SA[i]=0;b=&t;i=n-1;j=n;m=0;c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(n-1)]:((unsigned char*)T)[(n-1)]);do{c1=c0;}while((0<=--i)&&((c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(i)]:((unsigned char*)T)[(i)]))>=c1));for(;0<=i;){do{c1=c0;}while((0<=--i)&&((c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(i)]:((unsigned char*)T)[(i)]))<=c1));if(0<=i){*b=j;b=SA+--B[c1];j=i;++m;do{c1=c0;}while((0<=--i)&&((c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(i)]:((unsigned char*)T)[(i)]))>=c1));}}if(1<m){if(flags&(16|32)){if(flags&16){if((D=((sais_index_type*)malloc((k*2)*sizeof(sais_index_type))))==NULL){if(flags&(1|4))free(C);if(flags&2)free(B);return-2;}}else D=B-k*2;++B[(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(j+1)]:((unsigned char*)T)[(j+1)])];for(i=0,j=0;i<k;++i){j+=C[i];if(B[i]!=j)SA[B[i]]+=n;D[i]=D[i+k]=0;}LMSsort2(T,SA,C,B,D,n,k,cs);name=LMSpostproc2(SA,n,m);if(flags&16)free(D);}else{LMSsort1(T,SA,C,B,n,k,cs);name=LMSpostproc1(T,SA,n,m,cs);}}else if(m==1){*b=j+1;name=1;}else name=0;if(name<m){if(flags&4)free(C);if(flags&2)free(B);newfs=(n+fs)-(m*2);if((flags&(1|4|8))==0){if((k+name)<=newfs)newfs-=k;else flags|=8;}RA=SA+m+newfs;for(i=m+(n>>1)-1,j=m-1;m<=i;--i){if(SA[i]!=0)RA[j--]=SA[i]-1;}if(sais_main(RA,SA,newfs,m,name,sizeof(sais_index_type),0)!=0){if(flags&1)free(C);return-2;}i=n-1;j=m-1;c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(n-1)]:((unsigned char*)T)[(n-1)]);do{c1=c0;}while((0<=--i)&&((c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(i)]:((unsigned char*)T)[(i)]))>=c1));for(;0<=i;){do{c1=c0;}while((0<=--i)&&((c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(i)]:((unsigned char*)T)[(i)]))<=c1));if(0<=i){RA[j--]=i+1;do{c1=c0;}while((0<=--i)&&((c0=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(i)]:((unsigned char*)T)[(i)]))>=c1));}}for(i=0;i<m;++i)SA[i]=RA[SA[i]];if(flags&4){if((C=B=((int*)malloc((k)*sizeof(int))))==NULL)return-2;}if(flags&2){if((B=((int*)malloc((k)*sizeof(int))))==NULL){if(flags&1)free(C);return-2;}}}if(flags&8)getCounts(T,C,n,k,cs);if(1<m){getBuckets(C,B,k,1);i=m-1,j=n,p=SA[m-1],c1=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(p)]:((unsigned char*)T)[(p)]);do{q=B[c0=c1];while(q<j)SA[--j]=0;do{SA[--j]=p;if(--i<0)break;p=SA[i];}while((c1=(cs==sizeof(sais_index_type)?((sais_index_type*)T)[(p)]:((unsigned char*)T)[(p)]))==c0);}while(0<=i);while(0<j)SA[--j]=0;}if(isbwt==0)induceSA(T,SA,C,B,n,k,cs);else pidx=computeBWT(T,SA,C,B,n,k,cs);if(flags&(1|4))free(C);if(flags&2)free(B);return pidx;}int sais(const unsigned char*T,int*SA,int n){if((T==NULL)||(SA==NULL)||(n<0))return-1;if(n<=1){if(n==1)SA[0]=0;return 0;}return sais_main(T,SA,0,n,UCHAR_SIZE,sizeof(unsigned char),0);}int sais_int(const int*T,int*SA,int n,int k){if((T==NULL)||(SA==NULL)||(n<0)||(k<=0))return-1;if(n<=1){if(n==1)SA[0]=0;return 0;}return sais_main(T,SA,0,n,k,sizeof(int),0);}
const int N=1e5+5;
char s[N];
int sa[N],r[N],h[N];
struct buf{
	char e[1<<25],*p;
	buf():p(e){}
	~buf(){fwrite(e,1,p-e,stdout);}
	void out(int x){
		static char z[12];
		char*i=z;
		if(!x)*p++=48;
		else{
			while(x){
				int y=x/10;
				*i++=x-y*10+48,x=y;
			}
			while(i!=z)*p++=*--i;
		}
		*p++=10;
	}
}it;
int main(){
	gets(s);
	int n=strlen(s);
	sais((unsigned char*)s,sa,n+1);
	for(int i=1;i<=n;++i)
		r[sa[i]]=i;
	for(int i=0,j=0;i<n;++i){
		if(j)--j;
		while(s[i+j]==s[sa[r[i]-1]+j])
			++j;
		h[r[i]]=j;
	}
	for(int i=1;i<=n;++i)
		it.out(sa[i]+1);
	for(int i=2;i<=n;++i)
		it.out(h[i]);
}

评测结果