1 概念

首先我们需要先定义后缀，这个其实很简单。我们定义后缀 \(i\) 表示以第 \(i\) 个字符开头的后缀，相当于 \(s[i,n]\)。

而后缀数组则主要关系到两个数组：\(sa\) 和 \(rk\)。其中 \(sa\) 表示将所有后缀按字典序排序后第 \(i\) 小的后缀的编号

（即后缀开头所在位置的下标），这就是后缀数组。而另一个 \(rk\) 则是一个辅助数组，表示后缀 \(i\) 的排名。

例如一个字符串 \(s=\) aabaaab，对后缀排序后结果应该如下：

1. \(s[4,7]\)，即 aaab。
2. \(s[5,7]\)，即 aab。
3. \(s[1,7]\)，即 aabaaab。
4. \(s[6,7]\)，即 ab。
5. \(s[2,7]\)，即 abaaab。
6. \(s[7,7]\)，即 b。
7. \(s[3,7]\)，即 baaab。

所以两个数组的值对应如下：

容易发现，我们会有如下性质：\(sa[rk[i]]=rk[sa[i]]=i\)。

2 求法

2.1 暴力法

根据上面的定义自然会想到这样一种做法：将所有后缀直接拎出来然后暴力排序。由于排序复杂度 \(O(n\log n)\)，而字符串比较是 \(O(n)\)，所以复杂度为 \(O(n^2\log n)\)。太劣。

2.2 倍增法

我们先来看这样一个问题：对于两个长度为 \(2n\) 的字符串 \(s,t\)。如果 \(s>t\) 当且仅当：

1. \(s[1,n]>t[1,n]\)。
2. \(s[1,n]=t[1,n]\) 且 \(s[n+1,2n]>t[n+1,2n]\)。

也就是说，对于长度为 \(2n\) 的字符串，如果我们已知所有长度为 \(n\) 的子串的排名，那么将前 \(n\) 位的排名看作第一关键字，后 \(n\) 位的排名看成第二关键字，直接排序就可以得到长度为 \(2n\) 的子串的排名。

这就给我们带来了启发，我们是不是也可以用这种方式来对后缀进行排序呢？事实上是可以的，考虑上述做法描述的就是一个倍增的模型，因此后缀数组的第二个求法就是倍增法。

具体求法如下：

1. 先对每个字符进行排序，得到此时的 \(sa_1\) 和 \(rk_1\) 数组。
2. 接下来用 \(rk_1[i]\) 和 \(rk_1[i+1]\) 作为排序的第一和第二关键字进行排序，就可以得到长度为二的子串的排名，得到 \(sa_2\) 和 \(rk_2\) 数组。
3. 按照这种方式，用长度为 \(w/2\) 的子串排名去倍增得到长度为 \(w\) 的子串排名。但是此时会有两个问题：我们在调用 \(rk_{w/2}[i+w/2]\) 时，\(i+w/2\) 可能大于 \(n\)，此时规定 \(rk_{w/2}[i+w/2]\) 的值是 \(0\)；同时，由于后缀 \(i\) 的长度可能本身就没有 \(w\)，那么子串 \(s[i,i+w-1]\) 就不存在。此时我们就将子串看作是 \(s[i,n]\) 即可。也就是每次倍增求出的其实是子串 \(s[i,\min(i+w-1,n)]\) 的排名。

这样重复倍增直到 \(w\ge n\) 时，得到的 \(sa_w\) 和 \(rk_w\) 就是我们需要的数组。

倍增的复杂度为 \(O(\log n)\)，排序复杂度 \(O(n\log n)\)，所以复杂度为 \(O(n\log^2 n)\)。

发现此时复杂度瓶颈在于排序。巧就巧在，对于二元组的排序还确实有更优的排序方式。

2.3 基数排序优化

2.3.1 基数排序

由于常用的排序无非就是快排或归排，所以在此不得不学习一下基数排序。

基数排序是桶排序的一种，它是针对于多维的排序，对于每一维使用桶排然后从低到高求解。

例如对于 \(11,32,39,50,103,9\) 进行排序。我们可以将个位看作第一维，十位看作第二维，百位看作第三维（也就是维度从低到高代表重要度从低到高）。排序过程如下：

首先对个位进行桶排：

然后按照十位数排序，注意如果同一个桶里面有几个数，按照上面的顺序放入：

最后按百位排序：

最后按顺序取出即可得到排序结果。

我们说明一下正确性：当我们排到第 \(k\) 维时，比 \(k\) 低的维都应该排好。如果第 \(k\) 维的值相同，那么比的就是 \(k\) 维以下的大小。所以在放入桶的时候要按照之前的顺序放入；而如果第 \(k\) 维的值不同，那么自然第 \(k\)​ 维更大的就更大。

根据上面的过程我们知道，对于一次桶排，时间复杂度为 \(O(n+a)\)，其中 \(a\) 维一次桶排的值域。而如果要进行 \(m\) 个维度的排序，复杂度就是 \(O(nm+\sum a)\)。

基数排序的铺垫就说完了，下面回到后缀数组的求解。

2.3.2 基数排序优化

我们上面提到过，对于 \(sa_k\) 和 \(rk_k\) 的排序是一个二维的排序，那么自然可以用基数排序。考虑此时的基数排序在时间复杂度中会有 \(m=2,a=n\)，所以此时的排序复杂度就降为 \(O(n)\)。总时间复杂度就是 \(O(n\log n)\)

代码如下：

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1e6 + 5;
const int Inf = 2e9;

string s;
int n, m, sa[Maxn], lsa[Maxn], rk[Maxn << 1], lrk[Maxn << 1], cnt[Maxn];
//rk 开双倍数组是为了让超出 n 的 i+w 的值为 0
//lsa 和 lrk 分别是拷贝的 sa 和 rk 

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> s;
	n = s.size();
	m = 128;//m 一开始要设成 z 的 ASCII 码左右 
	s = ' ' + s;
	for(int i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;
	//这里直接将排名设为字符，因此值域是 z 的 ASCII 码 
	for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
	for(int i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;//对一个字符进行桶排 
	for(int k = 1; k < n; k <<= 1, m = n/*注意第一次循环时 m 仍为 128*/) {
        //求解长度为 2k 的字符串
		//对于两个关键字进行基数排序
        //对于 rk[sa[i]+k] 进行桶排序（第二关键字） 
		memset(cnt, 0, sizeof cnt);
		for(int i = 1; i <= n; i++) lsa[i] = sa[i];//由于 sa 要更新，所以拷贝上一次的值 
		for(int i = 1; i <= n; i++) cnt[rk[lsa[i] + k]]++;
		for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
		for(int i = n; i >= 1; i--) sa[cnt[rk[lsa[i] + k]]--] = lsa[i];
		//对于 rk[sa[i]] 进行桶排序（第一关键字） 
		memset(cnt, 0, sizeof cnt);
		for(int i = 1; i <= n; i++) lsa[i] = sa[i];
		for(int i = 1; i <= n; i++) cnt[rk[lsa[i]]]++;
		for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
		for(int i = n; i >= 1; i--) sa[cnt[rk[lsa[i]]]--] = lsa[i];
		//此时得出的 sa 就是长度为 k 的子串的对应数组了 
		for(int i = 1; i <= n; i++) lrk[i] = rk[i];//由于 rk 要更新，所以拷贝上一次的值 
		for(int p = 0, i = 1; i <= n; i++) {
			if(lrk[sa[i]] == lrk[sa[i - 1]] && lrk[sa[i] + k] == lrk[sa[i - 1] + k]) {
				//如果排序之后两个关键字都相同，说明两者的排名也应该相同 
				rk[sa[i]] = p;
			}
			else {
				rk[sa[i]] = ++p;//否则就不相同 
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		cout << sa[i] << ' ';//直接输出最后结果即可 
	} 
	return 0;
}

2.4 常数优化

尽管上面代码理论复杂度为 \(O(n\log n)\)，但是它的常数其实很大，有可能会被卡掉。我们有如下常数优化：

1. 第二关键字无需桶排序

我们思考一下对于第二关键字排序的实质。在上文的代码中，rk[lsa[i]+k] 的值可能为 \(0\)。而如果为 \(0\)，则它必定是最小的。因此我们根本不用看它们，直接放到最开头即可。

接下来我们遍历排名从低到高，如果当前的 \(sa[i]>k\)，则说明它才能与之前的字符串拼成长为 \(2k\) 的字符串。由于我们本身就是按照排名遍历，所以此时直接插入 \(sa[i]-k\) 就是按照排名排好序的。

2. 值域限制

注意到上文我们每次都会计算出一个 \(p\) 值，而这个 \(p\) 值就是 \(rk\) 的值域，也就是基数排序的值域。

3. 判断是否生成后缀数组

考虑每次算出的 \(rk\) 数组，若值域已经为 \([1,n]\) 就说明每个排名都不同，此时直接跳出即可。

最终的代码如下：

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1e6 + 5;
const int Inf = 2e9;

string s;
int n, m, sa[Maxn], lsa[Maxn], rk[Maxn << 1], lrk[Maxn], cnt[Maxn];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> s;
	n = s.size();
	m = 128;
	s = ' ' + s;
	for(int i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;
	for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
	for(int i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;
	int p = 0;
	for(int k = 1; k < n; k <<= 1, m = p/*值域优化*/) { 
		int cur = 0;
		for(int i = n - k + 1; i <= n; i++) lsa[++cur] = i;//没有 i+k 的直接塞到前面 
		for(int i = 1; i <= n; i++) {
			if(sa[i] > k) {//能够与前面的拼成子串 
				lsa[++cur] = sa[i] - k;
			}
		}
		memset(cnt, 0, sizeof cnt);
		for(int i = 1; i <= n; i++) cnt[rk[lsa[i]]]++;
		for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
		for(int i = n; i >= 1; i--) sa[cnt[rk[lsa[i]]]--] = lsa[i];
		for(int i = 1; i <= n; i++) lrk[i] = rk[i];
		p = 0;
		for(int i = 1; i <= n; i++) {
			if(lrk[sa[i]] == lrk[sa[i - 1]] && lrk[sa[i] + k] == lrk[sa[i - 1] + k]) {
				rk[sa[i]] = p;
			}
			else {
				rk[sa[i]] = ++p; 
			}
		}
		if(p == n) break;//直接跳出即可 
	}
	for(int i = 1; i <= n; i++) {
		cout << sa[i] << ' ';
	} 
	return 0;
}

3 应用

似乎后缀数组都和后缀有关，那么有关前缀的内容怎么办呢？我们还需要一个神奇的东西。

3.1 height 数组

定义两个字符串的最长公共前缀（LCP）为满足 \(s[1,x]=t[1,x]\) 的最大的 \(x\)。此时定义 \(LCP(i,j)\) 表示后缀 \(i\) 和后缀 \(j\) 的最长公共前缀的长度。

接下来我们定义 \(height[i]=LCP(sa[i],sa[i-1])\)，也就是第 \(i\) 名后缀与它前一名的后缀的 LCP 的长度。规定 \(height[1]=0\)。

现在我们需要考虑如何求出 \(height\) 数组，显然 \(O(n^2)\) 的算法是显然的，不过我们有线性算法。

引理：\(height[rk[i]]\ge height[rk[i-1]]-1\)。

证明：

当 \(height[rk[i-1]]\le 1\) 时，右边小于等于 \(0\)，上式显然成立。

否则，根据 \(height\) 定义，有 \(height[rk[i-1]]=LCP(sa[rk[i-1]],sa[rk[i-1]-1])>1\)。

不难发现括号中左边就是后缀 \(i-1\)，也就是说后缀 \(i-1\) 与后缀 \(sa[rk[i-1]-1]\) 有长度为 \(height[rk[i-1]]\) 的 LCP，于是不妨用 \(aA\) 来表示这个 LCP（\(a\) 为一个字符，\(A\) 显然为一个非空的字符串，长度为 \(height[rk[i-1]]-1\)）。

那么后缀 \(i-1\) 可以表达为 \(aAD\)，后缀 \(sa[rk[i-1]-1]\) 可以表示为 \(aAB\)（其中 \(B<D\)，\(B\) 可能为空，\(D\) 一定非空）。进一步的，后缀 \(i\) 就可以被表达为 \(AD\)，且存在后缀 \(sa[rk[i-1]-1]+1\) 为 \(AB\)。

因为后缀 \(sa[rk[i]-1]\) 在大小排名上只比后缀 \(sa[rk[i]]\) 小一位，而 \(AB<AD\)，所以 \(AB\le\) 后缀 \(sa[rk[i]-1]\) \(< AD\)。此时显然后缀 \(i\) 与后缀 \(sa[rk[i]-1]\) 有共同前缀 \(A\)。

于是 \(height[rk[i]]=LCP(sa[rk[i]],sa[rk[i]-1])=LCP(i,sa[rk[i]-1])\ge|A|=height[rk[i-1]]-1\)。引理得证

根据上面的引理，我们就可以直接求出 \(height\) 数组：

int k = 0;
for(int i = 1; i <= n; i++) {
	if(rk[i] == 0) continue;
	if(k) k--;//k 就是 ht[rk[i-1]]，显然当前的 ht[rk[i]] >= k-1（根据引理） 
	while(s[i + k] == s[sa[rk[i] - 1] + k]) k++;//再暴力看 k 能扩展到哪里 
	ht[rk[i]] = k;//赋值即可 
}

显然 \(k\) 不会大于 \(n\)，同时 \(k\) 最多减 \(n\) 次，因此最多加 \(2n\) 次，复杂度就为线性。

3.2 应用

现在有了 \(sa,rk,height\) 这三个数组，可以说很多字符串题都可以做了。下面简单举几个后缀数组和 height 数组的应用。

3.2.1 求 LCP

上面我们一直在说 LCP，那么现在来看怎样求出两个子串的 LCP。

LCP 引理：定义 \(LCP(i,j)\) 表示 \(sa[i]\) 与 \(sa[j]\) 的 LCP，则有 \(LCP(i,j)=\min(LCP(i,k),LCP(k,j))(i\le k\le j)\)。

证明：

考虑反证法。假设 \(p=\min(LCP(i,k),LCP(k,j))\)，则 \(LCP(i,k)\ge p,LCP(k,j)\ge p\)。设后缀 \(sa[i]\) 为 \(u\)，后缀 \(sa[j]\) 为 \(v\)，后缀 \(sa[k]\) 为 \(w\)。

于是有 \(u,w\) 前 \(p\) 个字符相等，\(v,w\) 前 \(p\) 个字符相等。所以 \(u,v\) 前 \(p\) 个字符相等，即 \(LCP(i,j)\ge p\)。

设 \(LCP(i,j)=q\)，且 \(q>p\)。则 \(q\ge p+1\)，且 \(u_{p+1}=v_{p+1}\)。

由于 \(p=\min(LCP(i,k),LCP(k,j))\)，所以 \(u_{p+1}\ne w_{p+1}\) 或 \(v_{p+1}\ne w_{p+1}\)。于是 \(u_{p+1}\ne v_{p+1}\)。矛盾！

故原假设不成立，则 \(q\le p\)，即 \(LCP(i,j)\le p\)。

所以 \(LCP(i,j)=p=\min(LCP(i,k),LCP(k,j))\)。

LCP 定理：\(LCP(i,j)=\min\limits_{k=i+1}^j(LCP(k-1,k))\)。

证明：

考虑数学归纳法。由 LCP 引理，\(LCP(i,i+1)=\min(LCP(i,i),LCP(i,i+1))\)​。

加入我们已经证明 \(LCP(i,j)=\min\limits_{k=i+1}^j(LCP(k-1,k))\)，那么可以推出 \(LCP(i,j+1)=\min(LCP(i,j),LCP(j,j+1))\min\limits_{k=i+1}^{j+1}(LCP(k-1,k))\)。

定理得证。

根据 LCP 定理，\(LCP(i,j)=\min\limits_{k=i+1}^j(LCP(k-1,k))=\min\limits_{k=i+1}^j(LCP(sa[k-1],sa[k]))=\min\limits_{k=i+1}^jheight[k]\)。于是 LCP 问题现在就转化为了 \(height\) 数组上的 RMQ 问题，利用 ST 表求解即可。