后缀数组哪里难？

前言

杂谈

感谢

2009年国家集训队论文

后缀数组 最详细讲解

luoguP3809 【模板】后缀排序 题解

luoguP2408 不同子串个数 题解

以及

来自ZhengRuIOI的课件

让本蒟蒻大概明白了这种算法

什么是后缀数组？

后缀数组指的是一个一维的数组，将一个给定的字符串的每一个后缀以其起始位置作为编号，按照字典序的大小排好序后放到一个数组中，我们便得到了一个后缀数组。

有什么用？

后缀数组——处理字符串的有力工具

——罗穗骞

如上所述，后缀数组可以解决许多花里胡哨的字符串问题，尤其是子串相关问题。后缀数组相较后缀自动机更易实现，且有更优秀的空间复杂度，而且许多后缀自动机的操作后缀数组都能完成。

实现方法

一般通用的方法有倍增法与DC3法，倍增法的时间复杂度为$O(logn)$，而DC3法则以思维难度的提升与代码实现方式的复杂化使时间复杂度提升为$O(n)$。

由于本人过于菜(懒)，在本文章中暂时只介绍倍增法。

配套食用

单纯的后缀数组虽然看上去非常牛，但是我们一般不仅仅要需要后缀的信息，更希望知道子串的相关信息，这时，就要用到LCP（最长公共前缀）这种奇妙的东西和$height$数组了。

具体实现

数组设定

后缀数组相交于以前学过的其他算法，有着更加复杂的数组设定，下面加以综述。

$sa[i]$：排好序的后缀数组第$i$位的后缀开头位置

$rk[i]$：开头位置为$i$的后缀在后缀数组中的位置

$x[i]$：基数排序时的第一关键字排名（待会会讲）

$y[i]$：基数排序的第二关键字排名，同时也是在$sa$数组计算过程中存储的暂时排名

$c[i]$：基数排序所用的桶

$height[i]$：$sa[i]$与$sa[i-1]$的最长公共前缀

很明显$sa[i]$与$rk[i]$互为逆运算。

前置：基数排序

一种奇妙的可以实现$O(n)$ 排序的方法

与桶排类似，不过是将每一个数拆分成个位、十位…

先按照个位插入桶中，再逐个放入答案数组中，这样的一次操作可以保证个位有序。再按照十位插入桶中，放入答案数组中，这一次操作后会使十位有序，因为个位已经有序了，那么前两位就全部有序了。

值得注意的一点，在从桶中弹出的时候，应该倒序枚举($n \rightarrow 1$)，这样才能保证之前排好的顺序不会乱掉。

举个例子吧：

21 18 12 42 56 66 22 46

先按个位排

21
12 42 22
56 66 46
18

然后

21 12 42 22 56 66 46 18

再按十位排

12 18
21 22
42 46
56
66

得到答案

12 18 21 22 42 46 56 66

求后缀数组的倍增法（$SA()$）

我们要判断两个后缀的字典序，当然可以$O(n)$的去扫一遍，不过面对全部后缀，使用快速排序的话，$O(n^2 logn)$显然无法接受。这时，提出一种新的方法——倍增法，其做法是这样的：
首先针对每一位上的子串获得一个排名。

然后我们将第$i$位的排名与$i+1$位合并

在这个可爱的例子中，我们已经完成了排序，如果两次没有完成，那么就不断沿着当前点往后的$2^k$合并，很明显，如果每一个后缀的排名都不同的话，算法就可以停止了。

代码长这样

#define fr(i, j, k) for(register int i = j; i <= k; ++i)
#define rf(i, j, k) for(register int i = j; i >= k; --i)
void SA(){
	fr(i, 1, n)c[x[i] = a[i]]++;//塞到桶里
	fr(i, 2, m)c[i] += c[i - 1];//做个前缀和
	rf(i, n, 1)sa[c[x[i]]--] = i;//第一次的排名
	for(int k = 1; k <= n; k <<= 1){//枚举2的k次
		int num = 0;
		fr(i, n - k + 1, n)y[++num] = i;//最后的k个数很明显没有第二关键字，所以它们在y数组的最前面
		fr(i, 1, n)if(sa[i] > k)y[++num] = sa[i] - k;//如果当前的排名大于k，就可以作为别人的第二关键字，塞到第二关键字中
		fr(i, 1, m)c[i] = 0;
		fr(i, 1, n)c[x[i]]++;
		fr(i, 2, m)c[i] += c[i - 1];
		rf(i, n, 1)sa[c[x[y[i]]]--] = y[i], y[i] = 0;//基数排序
		swap(x, y);//准备通过旧的x生成新的x
		x[sa[1]] = 1;
		num = 1;
		fr(i, 2, n){
			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num; //通过排好序的sa[i]生成新的第一关键字
		}
		if(num == n)break;//排名全都不一样就可以退出了
		m = num;//数据的范围变成只有num个
	}
}

最大公共前缀（LCP）

其实后缀数组本身能解决的问题有限，我们很多时候都要与$LCP$和$height$数组配套使用。

怎么求$height$？

直接暴力$O(n)$求解每个$height[i]$显然不可行，但是某些极其牛的人证出了一条不那么显然的结论：

$$height[i] \ge height[i - 1] - 1$$

下面我来尝试以一种更加浅显的方式来证明。

首先考虑$i$在原串中的前一位$i-1$，再考虑$i-1$在后缀数组中的前一位$k$。
很明显分一下两种情况：
第一种情况$k$与$i-1$没有公共前缀，即$height[i-1] == 0$，此时结论显然成立。

第二种情况如上图，$k$与$i-1$有公共前缀，即$height[i] \not= 0$。此时考虑k在原串中的后一位$k+1$与$i$之间的公共前缀，可以明显地得到以下结论：

1.在排好序的后缀数组中，$k+1$在$i$的前面。(因为$k+1$是$k$的后缀，$i$是$i-1$的后缀)

2.$k+1$与$i$之间的最长公共前缀为$height[i-1]-1$

那么也就说明了，$height[i]$的大小至少为$height[i-1]-1$，因为如果有一个后缀插在$k+1$与$i$中间的话，它与$i$的最长公共公共前缀不可能会比$k+1$与$i$的最长公共前缀小。就这样，我们得到了一个$O(n)$的解法来求解$height$数组。

代码

void get_height(){
	int k = 0, j;
	fr(i, 1, n)rk[sa[i]] = i;//获取排名
	fr(i, 1, n){
		j = sa[rk[i] - 1];//j是i在sa数组中的前一位
		if(k) k--;//因为是>= height[i-1] - 1，所以要-1
		while(a[i + k] == a[j + k])k++;
		height[rk[i]] = k;
	}
}

一道模版题

luoguP3809 【模板】后缀排序


直接求出$sa$数组即可

代码

#include <bits/stdc++.h>
using namespace std;
#define fr(i, j, k) for(register int i = j; i <= k; ++i)
#define rf(i, j, k) for(register int i = j; i >= k; --i)
const int maxn = 1e6 + 10;
int m, n;
int x[maxn], y[maxn], c[maxn];
char s[maxn];
int sa[maxn], rk[maxn];
void SA(){
	fr(i, 1, n)c[x[i] = s[i]]++;
	fr(i, 2, m)c[i] += c[i - 1];
	rf(i, n, 1)sa[c[x[i]]--] = i;
	for(int k = 1; k <= n; k <<= 1){
		int num = 0;
		fr(i, n - k + 1, n)y[++num] = i;
		fr(i, 1, n)if(sa[i] > k)y[++num] = sa[i] - k;
		fr(i, 1, m)c[i] = 0;
		fr(i, 1, n)c[x[i]]++;
		fr(i, 2, m)c[i] += c[i - 1];
		rf(i, n, 1)sa[c[x[y[i]]]--] = y[i], y[i] = 0;
		swap(x, y);
		x[sa[1]] = 1;
		num = 1;
		fr(i, 2, n){
			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
		}
		if(num == n)break;
		m = num;
	}
	fr(i, 1, n)printf("%d ", sa[i]);
}
int main(){
	gets(s+1);
	n = strlen(s + 1);
	m = 122;
	SA();
}