• 一些 Update
• 1. 概述
• 2. 子串
• 3. sa 数组和 Rank 数组
  • 1. 定义
  • 2. 求 Rank 数组
    • 2.1 暴力
    • 2.2 倍增算法
      • 2.2.1 倍增+快排
      • 2.2.2 倍增+基排
  • 3. 代码
• 4. height 数组
  • 1. 定义
  • 2. 求法
• 5. 总结

一些 Update

Update 2022/2/8：修正了部分语言，不影响阅读与理解。

1. 概述

后缀数组（SA），是一种强而有力的字符串算法。其优秀的性质使得其能够代替大部分字符串算法，受到广大 OIer 的欢迎。

2. 子串

在讲后缀数组之前，我们先讲一讲子串这个概念。

一般情况下，我们认为子串就是一个字符串中的一部分连续字符组成的字符串，但是在运用后缀数组的时候子串更多时候被视为后缀的前缀。

比如说一个串 \(s\)，子串 \(s_{l...r}\) 会被看作 \(s_{l...|s|}\) 的前缀，下文会用到这个点。

3. sa 数组和 Rank 数组

1. 定义

在后缀数组中，sa 数组和 Rank 数组是求 height 数组的基础。

\(sa[]\)：\(sa_i\) 表示的是排名为 \(i\) 的后缀为 \(sa_i\)。

\(Rank[]\)：\(Rank_i\) 表示第 \(i\) 个后缀的排名为 \(Rank_i\)。

这里我们规定 \(s_{n...n},s_{n-1...n},...,s_{1...n}\) 分别为第 1、2、……、\(n\) 个后缀。

那么从上面我们可以看出来：\(Rank[sa[i]]=sa[Rank[i]]=i\)。

因此我们只要求 1 个就好，由于 \(Rank\) 数组好求，那么我们求 \(Rank\) 数组。

2. 求 Rank 数组

求 \(Rank\) 数组有 4 种方法：

1. 暴力，时间复杂度 \(O(n^2 \log n)\)
2. 倍增算法+快速排序，时间复杂度 \(O(n \log^2 n)\)
3. 倍增算法+基数排序，时间复杂度 \(O(n \log n)\)
4. DC3 算法，时间复杂度 \(O(n)\)，但常数较大，在 OI 中不比倍增算法优。

本篇博文不对 DC3 算法展开阐述，有兴趣的读者可以自行查阅相关资料。

2.1 暴力

这还需要我说吗qwq，快排的时间复杂度为 \(O(n \log n)\)，比较两个字符串的大小的平均时间复杂度是 \(O(n)\)，结果就是 \(O(n^2 \log n)\)。

2.2 倍增算法

那么我们看看倍增算法如何操作。

比如当前字符串为 aabaaaab。

第一步：我们取步长为 0，进行排序，如下。

第二步：我们取步长为 \(1 \times 2 = 2\)。

相当于对于第 \(i\) 个后缀，我们取出前面 2 个字符然后排序。

此时，对于第 \(i\) 个后缀，取出的字符构成的集合为 \(s_{i,i+1}\)。

我们将其组合成一个二元组来排序，以第一个数字为第一关键字。

也就是说如果我们用一个结构体 \(q->\{a,b\}\) 来存，那么第 \(i\) 个位置的二元组 \(q_i={Rank_i,Rank_{i+1}}\)，其中 \(Rank\) 是上一轮的排名。

如果不存在 \(i+1\) 则为 0。

那么经过此次排序之后如下：

第三次：我们取步长为 \(2 \times 2 = 4\)。

那么对于第 \(i\) 个后缀，取出来比较的是 \(q_i=\{Rank_i,Rank_{i+2}\}\)。

为什么我们可以倍增呢？这也是倍增的精巧之处。

字符串的比较是按位比较，而在第一次排序中，我们规定字符串长度为 1，第二次规定为 2，此时在第三次比较中由于长度为 2 的字符串已经比较完了，因此我们可以将其取出整体比较而非单独比较，故而可以倍增。

排序之后如下：

第四次：取步长为 \(4 \times 2 = 8\)，此时我们需要取 \(q=\{Rank_i,Rank_{i+4}\}\) 来组合。

结果如下。

那么接下来因为步长超过 \(n\) 了，结束，\(Rank\) 数组处理完毕。

在正式写代码的时候我们可以预处理步长为 \(1\) 的情况，然后开始处理，同时代码里面 \(len=1\) 表示步长为 \(2 \times len = 2\)，注意一下。

\(sa\) 数组？那不是根据 \(sa[Rank[i]]=i\) 就可以解决了吗qwq

但是上面有一个遗留问题没有解决：我们怎么对二元组排序？

先分析一下时间复杂度：

假设排序时间复杂度不记，那么倍增 \(\log n\)，处理二元组 \(n\)，总时间复杂度为 \(O(n \log n)\)。

那么我们接下来考虑排序。

2.2.1 倍增+快排

这个是比较容易想到的思路，直接对二元组快排即可，复杂度 \(O(n \log n)\)，这样最后的复杂度为 \(O(n \log n + (\log n) \times (n \log n))=O(n \log^2 n)\)。

这样子会多一个 log，但是代码比基排要好写一点。

注意 luogu 的模板题用 cmp 函数快排会 TLE，需要重载运算符。

2.2.2 倍增+基排

对于这种位数小的二元组，我们可以使用基数排序来解决。

如果没有学过基排，您可以到 基数排序 - OI Wiki 上学习基排。

由于位数特别小，那么我们可以认为基排的时间复杂度近似于 \(O(n)\)，那么总时间复杂度为 \(O(n \log n)\)，但是代码会稍微长亿点。

3. 代码

倍增+快排：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int MAXN = 1e6 + 10;
char s[MAXN];
int n, rk[MAXN << 1], sa[MAXN << 1];//这里空间开两倍可以减少后面的特判
struct node
{
	int a, b, id;
	bool operator <(const node &t)const
	{
		return (a ^ t.a) ? (a < t.a) : (b < t.b);
	}//重载运算符
}q[MAXN];

int read()
{
	int sum = 0, fh = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') fh = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {sum = (sum << 3) + (sum << 1) + (ch ^ 48); ch = getchar();}
	return sum * fh;
}

int main()
{
	scanf("%s", s + 1);//处理方便从 1 开始
	int n = strlen(s + 1);
	for (int i = 1; i <= n; ++i) rk[i] = s[i];//预处理步长为 1
	for (int len = 1; len < n; len <<= 1)
	{
		for (int i = 1; i <= n; ++i) {q[i].a = rk[i]; q[i].b = rk[i + len]; q[i].id = i;}//首先处理二元组
		sort(q + 1, q + n + 1);
		int m = 0;//排名
		for (int i = 1; i <= n; ++i)
		{
			if (q[i].a != q[i - 1].a || q[i].b != q[i - 1].b) ++m;
			rk[q[i].id] = m;//重新处理 Rank 数组
		}
	}
	for (int i = 1; i <= n; ++i) sa[rk[i]] = i;//得到 sa 数组
	for (int i = 1; i <= n; ++i) printf("%d ", sa[i]);
	printf("\n"); return 0;
}

倍增+基排：我没写

4. height 数组

1. 定义

\(height_i\)：表示排名为 \(i - 1\) 的后缀与排名为 \(i\) 的后缀的最长公共前缀（LCP）长度。

比如还是 aabaaaab 这个字符串，如下所示。

那么又要怎么求 \(height\) 呢？

2. 求法

显然有一种朴素方法：\(O(n^2)\) 暴力匹配。

当然这样复杂度太高，需要优化。

这里再次引入一个数组：\(h\) 数组。

\(h_i\)：第 \(i\) 个后缀与排名在 \(i\) 前面的后缀的最长公共前缀长度。

还是看图。

\(h\) 数组有一个很重要的性质：$$h_i \geq h_{i-1} - 1,i \geq 2$$

证明：（以下证明取自国家集训队2009年论文）

首先，\(i=1\) 时 \(h_1=0\)，因为其前面没有后缀。

那么对于 \(i \geq 2\)，假设第 \(k\) 个后缀是排在 \(i-1\) 前一名的后缀，那么最长公共前缀长度为 \(h_{i-1}\)。而第 \(k+1\) 个后缀是排在 \(i\) 前面的，最长公共前缀长度为 \(h_{i-1}-1\)，所以排在 \(i\) 前面一名的后缀与 \(i\) 的最长公共前缀长度至少为 \(h_{i-1}-1\)。

据此，我们重新回到 \(height\) 数组。

于是有了上面的性质，我们在求 \(height_i\) 的时候，可以证明前 \(h_{i-1}-1\) 个字符一定是相同的，这样就可以大大优化时间复杂度。

代码：

int k = 0;//记录 h[i-1]
for (int i = 1; i <= n; ++i)
{
	if (k) --k;//先 -1
	if (rk[i] == 1) continue;//排名为 1 的后缀不计 height
	int j = sa[rk[i] - 1];//取出上一个字符串
	while (s[j + k] == s[i + k]) k++;//匹配
	height[rk[i]] = k;//记录
}

5. 总结

后缀数组(SA)，巧妙使用倍增算法，充分利用字符串之间的性质，对后缀进行排序。

注意 SA 也可以是模拟退火的简称，别弄混。

一般情况下利用后缀数组求解字符串问题的时候我们都是利用 height 数组的，rank 数组和 sa 数组只是拿来求 height 的，不大会用到，然后一些 LCP 问题都是在 height 上做文章的，有些时候在一些约束条件下 height 会有规律（比如有序），这个时候就可以用一点 Trick 解题。