【模板·后缀数组/sa】洛谷 P3809 【模板】后缀排序

题目：后缀排序

代码：

#include<bits/stdc++.h>
using namespace std;

#define maxn 1000000

int n,m;
char a[maxn+5];

int sa[maxn+5],rk[maxn+5];
int tax[maxn+5],tp[maxn+5];

void readin() {
	scanf(\"%s\",a+1);
	n=strlen(a+1);
}

void rsort() {
	memset(tax,0,sizeof(tax));
	for(int i=1;i<=n;i++) tax[rk[tp[i]]]++;
	for(int i=1;i<=m;i++) tax[i]+=tax[i-1];
	for(int i=n;i>=1;i--) sa[tax[rk[tp[i]]]--]=tp[i];
}

void makesa() {
	for(int i=1;i<=n;i++) rk[i]=(int)a[i],tp[i]=i;
	rsort();
	for(int k=1;k<=n;k<<=1) {
		int num=0;
		for(int i=n-k+1;i<=n;i++) tp[++num]=i;
		for(int i=1;i<=n;i++) if(sa[i]>k) tp[++num]=sa[i]-k;
		rsort();
		swap(rk,tp);
		rk[sa[1]]=1;
		num=1;
		for(int i=2;i<=n;i++) {
			if(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k]) rk[sa[i]]=num;
			else rk[sa[i]]=++num;
		}
		if(num==n) break;
		m=num;
	}
}

int main() {
	readin();
	m=122;
	makesa();
	for(int i=1;i<=n;i++) printf(\"%d \",sa[i]);	
	return 0;
}