BZOJ 1031 JSOI2007 字符加密Cipher 后缀数组

题目大意：给定一个字符串，求将这个字符串首尾相接后以每个字符开头的字符串排序后最后一列的字符串

传说中的后缀数组0.0 昨晚看了一晚上DC3没看懂，于是写了倍增0.0 罗先生的25行代码实在是抽象QAQ 蒟蒻表示理解不能QAQ 于是自己写了个比较清晰的版本QAQ

首先这题是环 于是我们把字符串的前n-1个字符添加到这个字符串的尾端 然后就是后缀数组的事情了

求完这个之后按照后缀数组的顺序枚举每个开头看看是不是长度大于等于n就行了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 200200
using namespace std;
int n,rank[M],sa[M];
char s[M];
int X[M],Y[M];
void Get_Rank()
{
	int i,j,tot=0;
	static pair<char,int>t[M];
	for(i=1;i<=n;i++)
		t[i]=make_pair(s[i],i);
	sort(t+1,t+n+1);
	for(i=1;i<=n;i++)
	{
		if(i==1||t[i].first!=t[i-1].first)
			++tot;
		rank[t[i].second]=tot;
	}
}
void Radix_Sort(int key[],int order[])
{
	int i;
	static int sum[M],cnt[M],temp[M];

	memset(sum,0,sizeof sum);
	memset(cnt,0,sizeof cnt);
	for(i=1;i<=n;i++)
		sum[ key[i] ]++;
	for(i=1;i<=n;i++)
		sum[i]+=sum[i-1];
	for(i=1;i<=n;i++)
		temp[ sum[key[order[i] ]-1]+ ++cnt[ key[order[i] ] ] ]=order[i];
	memcpy(order,temp,sizeof temp);
}
void Prefix_Doubling()
{
	int i,j,tot;
	Get_Rank();
	for(j=1;j<=n;j<<=1)
	{
		for(i=1;i<=n;i++)
		{
			X[i]=rank[i];
			Y[i]=i+j>n?0:rank[i+j];
			sa[i]=i;
		}
		Radix_Sort(Y,sa);
		Radix_Sort(X,sa);
		for(i=1,tot=0;i<=n;i++)
		{
			if( i==1 || X[sa[i]]!=X[sa[i-1]] || Y[sa[i]]!=Y[sa[i-1]] )
				++tot;
			rank[sa[i]]=tot;
		}
	}
}
int main()
{
	int i;
	scanf("%s",s+1);
	n=strlen(s+1);
	memcpy(s+n+1,s+1,n-1);
	n=n+n-1;
	Prefix_Doubling();
	for(i=1;i<=n;i++)
		if(sa[i]+(n>>1)<=n)
			putchar(s[sa[i]+(n>>1)]);
	cout<<endl;
	return 0;
}