后缀数组 学习笔记

什么是后缀数组

我们将字符串 $s$ 的每个后缀按字典序排序，后缀数组 $sa[i]$ 就表示排名为 $i$ 的后缀的起始位置的下标。它的映射数组 $rk[i]$ 表示起始位置下标为 $i$ 的后缀的排名。
简单来说的话，$sa[i]$ 表示排名为 $i$ 的是什么，$rk[i]$ 表示第 $i$ 个的排名是什么。

这里显然有 $rk[sa[i]]=i,sa[rk[i]]=i$

如何求

首先最暴力的方法是对于每个后缀进行快排，复杂度接近 $O(n^2\log n)$。
一般来说，求 $sa$ 数组用的是倍增和基数排序。

先按照字典序排列，一一比较的话，肯定是从第一位开始比。我们可以用一个桶，记录每一个后缀的当前位在哪个桶中，然后进行排序。

可以用倍增进行优化，如果得到了第一位的排序，把第二位作为第二关键字，就可以得到第二位的排序。在得到第二位的排序之后，用倍增就可以得到第四位的排序。以此类推。最后的复杂度就是 $O(n\log n)$ 的。

具体分为四个块。

首先将数组名约定一下。$x[i]$ 为桶，$y[i]$ 为辅助数组，$c[i]$ 为计数数组。

    step 1
rep(i,1,n) c[x[i] = s[i]]++; //先按第一个字母编桶号并累加
rep(i,1,m) c[i] += c[i-1]; //前缀和操作
drep(i,n,1) sa[c[x[i]]--] = i; //后缀i的排序，是i所在的桶，的剩余累计值

for(re int k(1) ; k<=n ; k<<=1){ //倍增，进行logn轮
	
	step 2
	memset(c,0,sizeof(c)); //把计数数组清空
	rep(i,1,n) y[i] = sa[i]; //将辅助数组设为原先的sa数组
	rep(i,1,n) c[x[y[i]+k]]++; //向右偏移k位，获得第二关键字的桶号并累计
	rep(i,1,m) c[i] += c[i-1]; //同样前缀和
	drep(i,n,1) sa[c[x[y[i]+k]]--] = y[i]; //后缀y[i]的排序是第二关键字
										   //所在桶号，的剩余累计值
	
	step 3
	memset(c,0,sizeof(c));
	rep(i,1,n) y[i] = sa[i];
	rep(i,1,n) c[x[y[i]]]++; //获得第一关键字的桶号并累计
	rep(i,1,m) c[i] += c[i-1];
	drep(i,n,1) sa[c[x[y[i]]]--] = y[i]; //后缀y[i]的排序是第一关键字
										 //所在桶号，的剩余累计值
	//注意这里循环要倒着来，因为我们对于第二关键字是从小到大排序的
	//倒着来，就相当于对于第一关键字相同的后缀，按第二关键字从大到小枚举
	//这样就能保证，第二关键字大的一定在第二关键字小的的后面
	
	//这两步操作，就相当于，对于两个关键字进行排序，先按第一关键字排序
	//然后再按第二关键字排序，这样就相当于对于已有的排好序了

	step 4
	rep(i,1,n) y[i] = x[i]; //记录原来的桶数组
	m = 0;
	rep(i,1,n){
		if(y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k]) x[sa[i]] = m; //如果这两个相同，就说明还是在一个桶中
		else x[sa[i]] = ++m; //重新编桶号
	}
	if(m == n) break; //已经在n个桶中，就说明已经排好序了
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

$height$数组

首先名次数组 $rk[i]$ 表示后缀 $i$ 的排名。

高度数组 $height[i]=LCP(sa[i],sa[i-1])$，即第 $i$ 名后缀与第 $i-1$ 名后缀的最长公共前缀长度。

首先我们要知道的是，后缀 $i$ 的前邻后缀一定是 $sa[rk[i]-1]$，因为 $i=sa[rk[i]]$，$i$ 的排名为 $rk[i]$，排名减 $1$ 取 $sa$ 即得。

暴力的话复杂度是 $O(n^2)$ 的。

这里我们需要用到一个定理：$height[rk[i]]\ge height[rk[i-1]]-1$

这样的话我们就能在 $O(n)$ 的时间内求出 $height$ 数组。

inline void get_height(){
	rep(i,1,n) rk[sa[i]] = i; //先映射一下rk数组
	int k = 0;
	rep(i,1,n){
		if(rk[i] == 1) continue; //因为排名为1的前面没有东西，height数组就是0
		if(k) k--; //根据上面的定理，先减一
		int j = sa[rk[i]-1]; //这个就是后缀i的前邻后缀
		while(i+k <= n && j+k <= n && s[i+k] == s[j+k]) k++; //暴力判断是否相等
		height[rk[i]] = k; //赋值
	}
}
1
2
3
4
5
6
7
8
9
10
11