后缀数组（SA）

约定

• 字符串的下标从 $1$ 开始。
• “后缀 $i$”表示从 $i$ 开始的后缀。

后缀数组

$\mathrm{sa}[i]$ 表示将所有后缀排序后第 $i$ 小的后缀的编号。$\mathrm{rk}[i]$ 表示后缀 $i$ 的排名。

性质：$\mathrm{sa}[\mathrm{rk}[i]]=\mathrm{rk}[\mathrm{sa}[i]]=i$。

求法 1：直接排序，$O(n^2 \log n)$

略

求法 2：将每个后缀插入到 Trie 上，$O(n^2)$

略

求法 3：倍增 + 快速排序，$O(n \log^2 n)$

先对每个长度为 $1$ 的子串进行排序。

令 $\mathrm{rk}_w[i]$ 表示长度为 $w$（结尾被截断的除外）的子串 $s[i \ldots \min\{i+w-1,n\}]$ 在 $\{s[i \ldots \min\{i+w-1,n\}]|s \in [1,n]\}$ 中的排名。

假设现在已知 $\mathrm{rk}_w$ 的值，要倍增以求出 $\mathrm{rk}_{2w}$ 的值。以 $\mathrm{rk}_w[i]$ 为第一关键字，以 $\mathrm{rk}_w[i+w]$ 为第二关键字（如果 $i+w>n$，则令 $\mathrm{rk}_w[i+w]=-\infty$），使用快速排序。总共倍增 $O(\log n)$ 次，每次是 $O(n \log n)$，总时间复杂度为 $O(n \log^2 n)$

提交记录（Luogu） 提交记录（LOJ） 备份

求法 4：倍增 + 基数排序，$O(n \log n)$

将前面使用的快速排序改为基数排序，对排名（值域为 $n$）进行双关键字排序，单次排序的时间复杂度为 $O(n)$，时间复杂度为 $O(n \log n)$。

提交记录（Luogu） 提交记录（LOJ） 备份

求法 5：SA-IS 算法，$\Theta(n)$

可以参考 诱导排序与 SA-IS 算法。

求法 6：DC3 算法，$O(n)$

可以参考 [2009]后缀数组——处理字符串的有力工具 by. 罗穗骞。

$\mathrm{height}$ 数组

最长公共前缀（LCP）

定义

两个字符串 $S$ 和 $T$ 的 LCP 就是最大的 $x$（$x \le \min\{|S|,|T|\}$）使得 $\forall i \in [1,x],S_i=T_i$。

下文中以 $\operatorname{lcp}(i,j)$ 表示后缀 $i$ 和后缀 $j$ 的最长公共前缀（的长度）。

性质

LCP Lemma

对于任意的 $1 \le \mathrm{rk}[i]<\mathrm{rk}[j]<\mathrm{rk}[k] \le n$，$\operatorname{lcp}(i,k)=\min\{\operatorname{lcp}(i,j),\operatorname{lcp}(j,k)\}$。

证明：设 $x=\min\{\operatorname{lcp}(i,j),\operatorname{lcp}(j,k)\}$，由定义得，后缀 $i$ 和后缀 $j$ 的前 $x$ 个字符相等，后缀 $j$ 和后缀 $k$ 的前 $x$ 个字符相等，那么后缀 $i$ 和后缀 $k$ 的前 $k$ 个字符相等，即 $\operatorname{lcp}(i,k) \ge x$。

接下来证明 $\operatorname{lcp}(i,k)=x$。用反证法，如果 $\operatorname{lcp}(i,k)=y>x$，那么后缀 $i$ 和后缀 $k$ 的第 $x+1$ 个字符相等，因为 $\mathrm{rk}[i]<\mathrm{rk}[j]<\mathrm{rk}[k]$，所以后缀 $i$、后缀 $j$ 和后缀 $k$ 的第 $x+1$ 个字符相等，矛盾。

LCP Theorem

对于任意的 $\mathrm{rk}[i]<\mathrm{rk}[j]$，$\operatorname{lcp}(i,j)=\min\limits_{\mathrm{rk}[i]<\mathrm{rk}[k] \le \mathrm{rk}[j]}\{\operatorname{lcp}(k-1,k)\}$。

证明：用 LCP Lemma 归纳证明即可。

$\mathrm{height}$ 数组

$\mathrm{height}[i]=\operatorname{lcp}(\mathrm{sa}[i],\mathrm{sa}[i-1])$，即第 $i$ 名的后缀与它前一名的后缀的最长公共前缀。特别地，$\mathrm{height}[1]=0$。

引理：$\mathrm{height}[\mathrm{rk}[i]] \ge \mathrm{height}[\mathrm{rk}[i-1]]-1$

证明：

• 当 $\mathrm{height}[\mathrm{rk}[i]] \le 1$ 时，上式显然成立。
• 当 $\mathrm{height}[\mathrm{rk}[i]]>1$ 时：设后缀 $i-1$ 为 $aAD$（$a$ 是一个字符，$A$ 为一个长度为 $\mathrm{height}[\mathrm{rk}[i-1]]-1$ 的字符串，$D$ 为剩余部分），那么后缀 $i$ 为 $AD$。设后缀 $\mathrm{sa}[\mathrm{rk}[i-1]-1]$ 为 $aAB$，那么 $\operatorname{lcp}(i-1,\mathrm{sa}[\mathrm{rk}[i-1]-1])=aA$。由于后缀 $\mathrm{sa}[\mathrm{rk}[i-1]-1]+1=AB$，一定排在后缀 $i$ 的前面，所以后缀 $\mathrm{sa}[\mathrm{rk}[i]-1]$ 一定含有前缀 $A$，所以 $\operatorname{lcp}(i,\mathrm{sa}[\mathrm{rk}[i]-1]) \ge \mathrm{height}[\mathrm{rk}[i-1]]-1$。

线性求法

$k$ 的最大值为 $n$，最多减小 $n$ 次，时间复杂度为 $O(n)$。

for(int i=1,k=0;i<=n;i++){
	if(k)k--;
	while(s[i+k]==s[sa[rk[i]-1]+k])k++;
	ht[rk[i]]=k;
}

例题