【学习笔记】后缀数组

容易忘记这个东西，干脆写篇博客把关键的地方讲清楚。（个人笔记向）

void getsa(){
	int len=123;
	for(int i=1;i<=n;i++)cnt[id[i]=s[i]]++;
	for(int i=1;i<=len;i++)cnt[i]+=cnt[i-1];
	for(int i=1;i<=n;i++)sa[cnt[id[i]]--]=i;
	for(int k=1;k<=n;k=(k<<1)){
		int p=0;
		//sec:第二关键字排名为i的数第一关键字的位置。
		for(int i=n-k+1;i<=n;i++)sec[++p]=i;
		for(int i=1;i<=n;i++)if(sa[i]>k)sec[++p]=sa[i]-k;
		for(int i=1;i<=len;i++)cnt[i]=0;
		for(int i=1;i<=n;i++)cnt[id[i]]++;
		for(int i=1;i<=len;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--)sa[cnt[id[sec[i]]]--]=sec[i],sec[i]=0;
		swap(id,sec);
		id[sa[1]]=1,p=1;
		for(int i=2;i<=n;i++)id[sa[i]]=(sec[sa[i]]==sec[sa[i-1]]&&sec[sa[i]+k]==sec[sa[i-1]+k])?p:++p;
		if(p>=n)break;
		len=p;
	}
	return ;
}
void gethei(){
	int k=0;
	for(int i=1;i<=n;i++){
		if(par[i]==1)continue;
		if(k)k--;
		int j=sa[par[i]-1];
		while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k])k++;
		hei[par[i]]=k;
	}
	//关键性质是在原字符串中，后一位显然最多比前一位lcp少1，再和sa的前一位比较。
	return ;
}

有很多经典应用，常见Kruskal重构树。