代码

#include<bits/stdc++.h>

#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-funroll-loops")
#pragma GCC target("avx,sse4")

#define mms(a,n) memset(a,0,sizeof((a)[0])*(n))
#define mmp(a,b,n) memcpy(a,b,sizeof((b)[0])*(n))
#define lowbit(x) ((x)&-(x))
#define pb push_back
#define fi first
#define se second
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define fo(i,l,r) for(register int i=l,_lim_=r;i<=_lim_;i++)
#define fd(i,r,l) for(register int i=r,_lim_=l;i>=_lim_;i--)
#define fos(i,l,r,d) for(register int i=l,_lim_=r;i<=r;i+=d)
#define fol(i,l,r) for(register ll i=l,_lim_=r;i<=_lim_;i++)
#define fdl(i,r,l) for(register ll i=r,_lim_=l;i>=_lim_;i--)
#define fosl(i,l,r,d) for(register ll i=l,_lim_=r;i<=r;i+=d)
#define Clear(a) memset(a,0,sizeof(a))
#define Copy(a,b) memcpy(a,b,sizeof(b))
#define ALL(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ldb;
typedef double db;
typedef pair<ull,int> pi;

namespace io{
	const int L=(1<<21)+1;
	char ibuf[L],*iS,*iT,obuf[L],*oS=obuf,*oT=obuf+L-1,c,st[55];int f,tp;
	#ifdef whzzt
		#define gc() getchar()
	#else
		#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,L,stdin),(iS==iT?EOF:*iS++)):*iS++)
	#endif
	inline void flush(){fwrite(obuf,1,oS-obuf,stdout);oS=obuf;}
	inline void putc(char x){*oS++=x;if(oS==oT)flush();}
	template<class I>
	inline void gi(I&x){
		for(f=1,c=gc();c<'0'||c>'9';c=gc())if(c=='-')f=-1;
		for(x=0;c<='9'&&c>='0';c=gc())x=x*10+(c&15);x*=f;
	}
	template<class I>
	inline void print(I x){
		if(!x)putc('0');if(x<0)putc('-'),x=-x;
		while(x)st[++tp]=x%10+'0',x/=10;
		while(tp)putc(st[tp--]);
	}
	inline void gs(char*s,int&l){
		for(c=gc();c<'a'||c>'z';c=gc());
		for(l=0;c<='z'&&c>='a';c=gc())s[l++]=c;
	}
	inline char O(){
		for(c=gc();c!='C'&&c!='Q'&&c!='R';c=gc());
		return c;
	}
};
using io::putc;
using io::gi;
using io::gs;
using io::print;

const int N=100005;

char s[N];int n;
namespace DS{
	int h[N],x[N],m,j,t1[N],t2[N],t3[N],*rk=t1,*sa=t2,*y=t3;
	void SA(){
		mms(x,(m=26)+1); 
		fo(i,1,n)x[rk[i]=s[i]-'a'+1]++;
		fo(i,1,m)x[i]+=x[i-1];
		fd(i,n,1)sa[x[rk[i]]--]=i;
		fos(l,1,n,l){
			fo(i,n-l+1,n)y[++x[rk[i]]]=i;
			fo(i,1,n)if(sa[i]>l)j=sa[i]-l,y[++x[rk[j]]]=j;
			swap(sa,y);
			x[m=y[sa[1]]=1]=0;
			fo(i,2,n){
				if(rk[sa[i]]!=rk[sa[i-1]]||rk[sa[i]+l]!=rk[sa[i-1]+l])x[++m]=i-1;
				y[sa[i]]=m;
			}
			swap(rk,y);
			if(m==n)break;
		}
		j=0;
		fo(i,1,n){
			while(s[i+j]==s[sa[rk[i]-1]+j])j++;
			h[rk[i]]=j;j-=!!j;
		}
	}
};

int main(){
	gs(s+1,n);
	DS::SA();
	fo(i,1,n)print(DS::sa[i]),putc(" \n"[i==n]);
	fo(i,2,n)print(DS::h[i]),putc(" \n"[i==n]);
	io::flush();
	return 0;
}

评测结果