后缀数组 SA-IS 算法 - 洛谷保存站

$\text{1\,Introduction}$

本文主体部分翻译自 Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009):[ Linear Suffix Array Construction by Almost Pure Induced-Sorting](https://local.ugene.unipro.ru/tracker/secure/attachment/12144/Linear+Suffix+Array+Construction+by+Almost+Pure+Induced-Sorting.pdf)，并加入了一些个人内容。

提供目前关于这篇论文的一个[翻译版本](https://riteme.site/blog/2016-6-19/sais.html)。

后缀数组问题：给定一个字符串，求出一个数组 $SA$，$SA[i]$ 表示将所有后缀按字典序升序排序后第 $i$ 小的后缀的编号，$SA$ 即为后缀数组。

众所周知，解决后缀数组（SA）问题的方法有易于实现的二分+哈希的 $\Theta(n\log^2 n)$ 做法，$\Theta(n\log n)$ 的倍增法，$\Theta(n)$ 的 DC-3，KA 等算法。

SA-IS（Suffix Array Construction by Almost Pure Induced-Sorting）算法是目前时空效率最高的一种 $\Theta(n)$ 算法，并且易于实现（原文表述“不到一百行 C 代码”），本文将会介绍此算法的实现原理。

---

$\text{2\,Reducing the Problem}$

下文除特殊说明外，字符或字符串之间的比较按字典序升序比较。

设 $S$ 是一个长度为 $n$ 的字符串，下标由 $0$ 到 $n-1$。除此之外， $S$ 有一个终止符 $\texttt{*}$ （位于下标 $n-1$ 处）。

设 $suf(S,i)$ 为 $S$ 开始于 $S[i]$ 的后缀。特殊地，$suf(S,n-1)$ 为单独的一个 $\texttt{*}$。

若 $suf(S,i)<suf(S,i+1)$，定义 $suf(S,i)$ 为 S 型后缀，

若 $suf(S,i)>suf(S,i+1)$，定义 $suf(S,i+1)$ 为 L 型后缀。

对应地，如果 $suf(S,i)$ 为 S 型后缀，定义 $S[i]$ 为 S 型，特殊地，$suf(S,n-1)$ 为 S 型后缀。

如果 $suf(S,i)$ 为 L 型后缀，定义 $S[i]$ 为 R 型。

由定义，可以观察到一个性质。

1.  $S[i]$ 为 S 型当且仅当以下两种情况：
 - $S[i]<S[i+1]$
 - $S[i]=S[i+1]$ 且 $suf(S,i+1)$ 为 S 型后缀。
2.  $S[i]$ 为 L 型当且仅当以下两种情况：
 - $S[i]>S[i+1]$
 - $S[i]=S[i+1]$ 且 $suf(S,i+1)$ 为 L 型后缀。

这里补充一下原文没有给的证明：

由定义，$suf(S,i)$ 为 S 型后缀等价于 $\exist k\in\{0,1,...,n-2-i\},S[i+k]<S[i+k+1]$ 且 $\forall k_0\in\{0,1,...,k\},S[i+k_0]=S[i+k_0+1]$。

下面证明 S 型的判断依据，L 型同理。

若 $S[i]<S[i+1]$ 立证，否则，条件等价于

$\exist k\in\{0,1,...,n-3-i\},S[i+k+1]<S[i+k+2]$ 且 $\forall k_0\in\{0,1,...,k\},S[i+k_0+1]=S[i+k_0+2]$

而我们令 $k^{'}=k+1,k_0^{'}=k_0+1$，则由等价条件，立证。

因此，我们可以将 $S$ 从右往左扫一遍，在 $\Theta(n)$ 的时间里确定每个位置是 S 型还是 L 型。

> **定义 2.1  LMS 字符**
> 
> 对于 $S[i],i\in[1,n-1]$，如果满足 $S[i]$ 为 S 型，$S[i-1]$ 为 L 型，
>
> 则称其为 LMS 字符（Leftmost S-type character）

> **定义 2.2  LMS 子串**
> 
> 一个 LMS 子串（LMS-substring）满足以下两个条件任一：
>
> 1. 是 $S$ 的一个子串 $S[i...j]$，其中 $S[i]$ 与 $S[j]$ 均为 LMS 字符。且 $S[i]\sim S[j]$ 无除 $S[i]$ 与 $S[j]$ 以外的其他 LMS 字符。
> 2. 终止符本身

我们将 LMS 子串作为原字符串的基础部分，如果我们可以高效地将所有 LMS 子串排列，我们可以用它们的排名来作为它们的名字使用。

结果就是，$S$ 变成了一个更短的串，我们用 $S_1$ 记录这些 LMS 子串的名称（也就是它们排序后的排名）。

这里举个例子：

$S=\texttt{mmiissiissiippii*}$，则 $S[2],S[6].S[10],S[16]$ 为 LMS 字符，

从而，$S[2...6],S[6...10],S[10...16],S[16]$ 是三个 LMS 子串，按照排名，将它们分别命名为 $2,2,1,0$，所以 $S_1=\{2,2,1,0\}$。

下面定义 LMS 子串之间的比较方式：

> **定义 2.3  LMS 子串的顺序**
> 
> 对于两个 LMS 子串，从左到右依次比较每个字符，
>
> 如果两个字符不同，按字典序升序排列，
>
> 否则，S 型排在 L 型之后。

定义 S 型与 L 型的依据在于：

在 $S[i]=S[j]$ 的前提下，如果 $S[i]$ 为 S 型，$S[j]$ 为 L 型，那么有 $suf(S,i)>suf(S,j)$。

为了排序所有的 LMS 子串，我们不需要额外的空间，相反，我们维护一个指针数组 $P_1$，其包含了 $S$ 中所有 LMS 子串的开头的下标。

可以通过从右到左扫一遍的方式在 $O(n)$ 时间内获得初始的 $P_1$。

> **定义 2.4  指针数组**
> 
> $P_1$ 是一个按照原始先后顺序（位置）排序的包含了所有 $S$ 中的所有 LMS 子串的起始位置的数组。
>
> （可能这里翻译的不好，放出原文）
>
>  $P_1$ is an array containing the pointers for all the
LMS-substrings in $S$ preserving their original positional order.

我们把所有 LMS 子串按照上文提到的排序方式排序后，之后我们再把 $P_1$ 中的每个元素的“名字”用其排序后的排名替代，这样我们就得到了一个新的字符串 $S_1$。

由上面的定义，可以观察到一个性质，如果两个 LMS 子串 $S[i...j],S[i^{'},...j^{'}]$ 的“名字”相同，当且仅当：

1. $j-i=j^{'}-i^{'}$
2. $S[i+k]=S[i^{'}+k],k\in[0,j-i]$
3. $t[i+k]=t[i^{'}+k],k\in[0,j-i]$

除此之外，还可以观察到几个性质：

> **引理 2.1 折半律**
>
> $||S_1||\le \dfrac{1}{2}||S||$。

正在渲染内容...