后缀数组SA模板详解

也许应该叫后缀排序，是求出\(sa[i]\)，\(rk[i]\)的一种算法。
\(sa[i]\)代表排名为i的后缀的开始位置。
\(rk[i]\)代表开始位置为\(i\)的后缀的排名。
这是实现比原理要复杂的算法。
先求出\(sa[i]\)之后再求出\(rk[i]\)。
考虑先求出长度为1时候的\(sa[i]\)数组。这个时候\(sa[i]\)代表长度为1排名为i的子串的开始位置。然后倍增求长度数为2时候的\(sa[i]\)数组。直到长度大于\(n\)（也就是字符串的长度）（超出长度的地方就是空字符）。然后考虑如何用长度为x时的\(sa[i]\)数组求长度为\(2x\)时的\(sa[i]\)数组。把长度为\(2x\)的串从中间劈开得到\(a\),\(b\)两个串，\(a,\)\(b\)的排名已经知道其实就是做一遍以\(a\)排名，\(b\)排名为第一第二关键字的排序。
知道\(sa[i]\)之后求\(rk[i]\)易如反掌，它们就是权值和下标相反的两个数组。
下面是求sa数组的代码。

void get_sa(){
	for(int i=1;i<=n;i++)c[x[i]=s[i]]++;
	for(int i=1;i<=m;i++)c[i]+=c[i-1];
	for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;
	for(int k=1;k<=n;k<<=1){
		int num=0;
		for(int i=n;i>=n-k+1;i--)y[++num]=i;//y[]第二关键字排名为num的第一关键字位置。 
		for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
		for(int i=1;i<=m;i++)c[i]=0;
		for(int i=1;i<=n;i++)c[x[i]]++;
		for(int i=1;i<=m;i++)c[i]+=c[i-1];
		for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;//第一第二关键字的基数排序 
		swap(x,y);
		num=0;
		for(int i=1;i<=n;i++)
			x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
		if(n==num)break;
		m=num;
	}
	for(int i=1;i<=n;i++)printf("%d ",sa[i]);
}

把代码拆开看

for(int i=1;i<=n;i++)c[x[i]=s[i]]++;
for(int i=1;i<=m;i++)c[i]+=c[i-1];
for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;

这里是基数排序，但不完全是基数排序。
它的作用是求出上面提到的长度为1时的\(sa\)数组。
\(s\)是原串数组，\(c\)是基数排序时用的桶，\(x[i]\)是\(i\)位置上的字符，\(m\)是编号的值域也就是桶的大小。
了解这个基数排序对了解后缀数组的实现十分重要。
第一个\(for\)是把出现的字符计数。第二个\(for\)是求前缀和。
考虑这个前缀和数组的意义是什么？
\(c[i]\)就是排名小于等于字符i的个数。换种说法\(c[i]\)是字符i的最大的排名。
假设桶长这样

求完前缀和之后长这样

从小到大
第一个出现的字母排第一，第二个出现的字母有三个，所以最大排名是4。。。
最后一个for就是把这些字符的排名求出。
至于为什么写，为什么要倒着循环，其实在求长度为1的串时并不重要。但之后以两个关键字排序时很重要

		int num=0;
		for(int i=n;i>=n-k+1;i--)y[++num]=i;//y[num]第二关键字排名为num的第一关键字位置。 
		for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;

y数组的意义在注释中。

比如要求长度为4的串，以最后一个点为开始的串后半部分完全是空的，排序一定是最靠前的，第一个循环主要处理这种情况。这里第一个循环正着反着循环都没问题。
第二个循环处理剩下部分

	for(int i=1;i<=m;i++)c[i]=0;
	for(int i=1;i<=n;i++)c[x[i]]++;
	for(int i=1;i<=m;i++)c[i]+=c[i-1];
	for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;

这个部分是基数排序。跟第一部分十分相似。
不过\(x\)数组代表以i开始的串的编号。
这里重点看最后一个循环，\(c[i]\)相当是求出了编号为\(i\)的串根据第一关键字排序的上界。
之后根据排好序的第二关键字倒着赋排名。
模拟一遍可以更好理解。

	swap(x,y);
	num=0;
	for(int i=1;i<=n;i++)
		x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
	if(n==num)break;
	m=num;

最后的部分就是根据排序结果赋给每个后缀新的编号。
当编号数位\(n\)时代表已经对所有的\(n\)个后缀完成了排序，程序就可以结束了。

\(height\)数组是常用的辅助数组（做做题就知道了）
\(height[i]\)代表排名为i的后缀与排名为\(i-1\)的后缀的最长公共前缀。
为了不产生混淆，写成\(height[rk[i]]\)。
如何求这个辅助数组？
直接求并不好求，但是有这个性质：\(height[rk[i]]=>height[rk[i-1]]-1\)
当\(height[rk[i-1]]<=1\)时这个式子显然成立。
考虑\(height[rk[i-1]]>1\)时

每个矩形代表一个后缀，在图中按字典序的大小排列放置。
下面的字母代表这个后缀在串中起始位置。
\(k+1\)和\(i\)代表的串其实是\(k\)与\(i-1\)代表的串砍去第一个字母。所以\(height[rk[i]]=>height[rk[i-1]]-1\)

总代码如下

#include
#include
#include
#include
#include
using namespace std;
const int N=2010000;
int c[N],x[N],y[N],sa[N],rk[N],height[N],n,m;
char s[N];
void get_sa(){
	for(int i=1;i<=n;i++)c[x[i]=s[i]]++;
	for(int i=1;i<=m;i++)c[i]+=c[i-1];
	for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;
	for(int k=1;k<=n;k<<=1){
		int num=0;
		for(int i=n;i>=n-k+1;i--)y[++num]=i;//y[]第二关键字排名为num的第一关键字位置。 
		for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
		for(int i=1;i<=m;i++)c[i]=0;
		for(int i=1;i<=n;i++)c[x[i]]++;
		for(int i=1;i<=m;i++)c[i]+=c[i-1];
		for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;//第一第二关键字的基数排序 
		swap(x,y);
		num=0;
		for(int i=1;i<=n;i++)
			x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
		if(n==num)break;
		m=num;
	}
	for(int i=1;i<=n;i++)printf("%d ",sa[i]);
}
void get_height(){
	for(int i=1;i<=n;i++)rk[sa[i]]=i;
	int k=0; 
	for(int i=1;i<=n;i++){//i是原串的下标 
		if(rk[i]==1)continue;
		if(k)k--;//height[rk[i]]>=height[rk[i-1]]-1 
		int j=sa[rk[i]-1];
		while(s[i+k]==s[j+k]&&i+k<=n&&j+k<=n)k++;
		height[rk[i]]=k;//height的下标是排名 
	}
	for(int i=1;i<=n;i++)printf("%d ",height[i]);
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	m=122;
	get_sa();
	get_height();
	return 0;
}