luogu3809 后缀排序 后缀数组

ref and 挑战程序设计竞赛。

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int n, cnt[1000005], rnk[1000005], saa[1000005], tmp[1000005], m=128, p;

char ss[1000005];

void sasort(){

	for(int i=0; i<m; i++)	cnt[i] = 0;

	for(int i=0; i<n; i++)	cnt[rnk[i]]++;

	for(int i=1; i<m; i++)	cnt[i] += cnt[i-1];

	for(int i=n-1; i>=0; i--)	saa[--cnt[rnk[tmp[i]]]] = tmp[i];//大约就是rnk[i]（第一关键字排序后的下标数组）定了一段一段的位置以后，依据第二关键字精确确定位置

}

void getSuffixArray(){

	for(int i=0; i<n; i++){

		rnk[i] = ss[i];

		tmp[i] = i;

	}

	sasort();

	for(int j=1; p<n; j<<=1){

		p = 0;

		for(int i=n-j; i<n; i++)	tmp[p++] = i;

		for(int i=0; i<n; i++)

			if(saa[i]>=j)

				tmp[p++] = saa[i] - j;//构造第二关键字数组，tmp[0]表示第二关键字最小（第0小）的元素位置i，（也就是i+j..n这样的后缀最小），以此类推

		sasort();

		swap(rnk, tmp);//因为以前的rank也要用到

		p = 1;

		rnk[saa[0]] = 0;

		for(int i=1; i<n; i++)

			if(tmp[saa[i-1]]==tmp[saa[i]] && tmp[saa[i-1]+j]==tmp[saa[i]+j])//这里是不会越界的……

				rnk[saa[i]] = p - 1;

			else

				rnk[saa[i]] = p++;

		m = p;//p代表有多少种rank，m代表字符集个数

	}

}

int main(){

	scanf("%s", ss);

	n = strlen(ss);

	ss[n++] = 0;

	getSuffixArray();

	for(int i=1; i<n; i++)

		printf("%d ", saa[i]+1);

	printf("\n");

	return 0;

}