sxczf's Blog

啊一只不知道正确性的模板。

刚写完还没应用过

找到错误了会改的（求找错。。。）

主要是看着

http://blog.csdn.net/xymscau/article/details/8798046

和http://wenku.baidu.com/link?url=cCmzid8m65q_x4MgP9QPPdyt-hY4auSH2tuFaYsz7e2vz3mAbq66WQ-YZ2z6bv2MRVOuh99DzVS8BIRT1vYvt5ziGEaP0ePhoZY3U6Z5Ff3

写（抄）的。。。

#include <cstdio>
#include <algorithm>
#define maxn 100005
using namespace std;
int a[maxn],b[maxn],c,d,e,f,g,h,i,j,k,l,m,n;
int R[maxn],K[maxn],cnt[maxn],up,rk[maxn],sa[maxn],id[maxn],height[maxn];

inline bool cmp(int *s,int a,int b,int l){return s[a]==s[b]&&s[a+l]==s[b+l];}

void getsa(){
	int d=1,p=0,*k=K,*r=R;
	for(i=up=0;i<n;i++)up=max(up,a[i]);up++;
	for(i=0;i<up;i++)cnt[i]=0;
	for(i=0;i<n;i++)cnt[k[i]=a[i]]++; k[n]=-1;
	for(i=0;i<up;i++)cnt[i+1]+=cnt[i];
	for(i=n-1;i>=0;i--)sa[--cnt[k[i]]]=i;
	for(;p<n;up=p,d<<=1){
		for(i=n-d,p=0;i<n;i++)r[p++]=i;
		for(i=0;i<n;i++)if(sa[i]>=d)r[p++]=sa[i]-d;
		for(i=0;i<up;i++)cnt[i]=0;
		for(i=0;i<n;i++)cnt[k[r[i]]]++;
		for(i=0;i<up;i++)cnt[i+1]+=cnt[i];
		for(i=n-1;i>=0;i--)sa[--cnt[k[r[i]]]]=r[i];
		swap(k,r);k[sa[0]]=0;
		for(i=1,p=1;i<n;i++)
		if(cmp(r,sa[i-1],sa[i],d))k[sa[i]]=p-1;
		else k[sa[i]]=p++;
	}
}
void getheight(){
	for(int i=0,p=0;i<n-1;i++){
		j=sa[rk[i]-1];
		while(a[i+p]==a[j+p])p++;
		height[rk[i]]=p;
		if(p)p--;
	}
}
int main(){
	freopen("in.in","r",stdin);
	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%d",&a[i]);
	a[n++]=0;
	getsa();
	getheight();
	for(i=0;i<n-1;i++)printf("%d ",sa[i]);printf("\n");
	for(i=0;i<n-1;i++)printf("%d ",height[i]);printf("\n");
	return 0;
}