【模板】后缀排序

int rk[N<<1],oldrk[N<<1];
pair<pair<int,int>,int> sa[N];
for(int i=1;i<=len;++i){
	sa[i].se=i;
	rk[i]=str[i];
}
for(int w=1;w<len;w<<=1){
	for(int i=1;i<=len;++i){
		int p=sa[i].se;
		sa[i]={{rk[p],rk[p+w]},p};
	}
	sort(sa+1,sa+len+1);
	memcpy(oldrk,rk,sizeof(rk));
	for(int rks=0,i=1;i<=len;++i){
		if(sa[i].fi==sa[i-1].fi)
			rk[sa[i].se]=rks;
		else rk[sa[i].se]=++rks;
	}
}