后缀数组_成型笔记

后缀数组

后缀数组，启动！

我发现大家学习算法的路径都是先打模板，然后练题，然后完全掌握，然后学习下一个算法。

但是我的算法学习是先把所有算法的模板抄一遍，然后过了两年看到自己 A 掉了模板想起来原来自己还学过这个东西。

虽然 $\text{SAM}$ 好像强于 $\text{SA}$，但似乎也有许多难以用 $\text{SAM}$ 做的事情。

可以发现，后缀数组实质上是后缀树的简化形式，失去了树形结构，但仍然能做许多后缀树能做的事情。

学一个算法的目的不在于贪图过几道模板题，而是去看在解决这类问题的时候有什么有用的思想。

朴素的后缀排序是 $\Theta(n\log ^2 n)$ 的，分治然后哈希优化快排，原理是使用 $(s_{[i,i+2^j)},s_{[i+2^j,i+2^{j+1}])})$ 的键值对排序可以得到 $s_{[i,i+2^{j+1})}$ 的顺序。

然后把快排换成基数排序就可以达到 $\Theta(n\log n)$，但是好长好长好长。

不恰当的比喻的话 $\text{SA}$ 可能就像 $\text{KMP}$，很多时候你宁愿打一个 $\text{ACAM}$ 也不愿打一个 $\text{KMP}$。

但掌握该思想是十分重要的，毕竟 NOI2023D2T2 就几乎无法在不构建后缀数组的前提下使用后缀树实现。

目录：

• 构建
• 例题 + 顺带总结
• 总结纯享版

构建

为了方便，称起始点为 $i$ 的后缀为 $\text{suf}_i$，$\text{len}_i=n-i+1$ 表示 $\text{suf}_i$ 的长度，称两个串 $a,b$ 的最长公共前缀为 $\text{lcp}(a,b)$。

需要介绍一些数组的含义：

$$\begin{aligned}&\text{sa}[i]\text{: 第 }i\text{ 名的后缀起始点是 sa}[i]\text{.}\\&\text{rk}[i]\text{: 起始点是 }i\text{ 的后缀排名是 rk}[i]\text{.}\\&\text{h}[i]\text{: 排名为 }i\text{ 的后缀和排名为 }i-1\text{ 的后缀的 lcp.}\end{aligned}$$

为了方便，称起始点为 $i$ 的后缀为 $\text{suf}_i$，则上述定义可以形式化定义为：

$$\begin{aligned}&\text{sa}[i]\text{: 第 }i\text{ 名的后缀是 suf}_{\text{sa}[i]}\text{.}\\&\text{rk}[i]\text{: suf}_i\text{ 的后缀排名是 rk}[i].\\&\text{h}[i]=\text{lcp}(\text{suf}_{\text{sa}[i]},\text{suf}_{\text{sa}[i-1]}).\end{aligned}$$

刚开始学后缀数组的时候是一定会傻傻分不清数组的，但这并不意味着你不适合学习后缀数组，对任何事情建立起一个惯有印象都是需要时间的，等你习惯了这些数组的含义，想忘记反而是一件难事。

（刚学 tarjan 时我看 tarjan 就像现在看后缀数组一样。）

一点小感想：文化课中很多时候老师并不会等每个人理解后再继续讲解，而并不是每个思路稍有卡顿的同学就完全跟不上了，就算你并不理解这个构造过程并且难以记忆，那么在尝试性默写和做题的帮助下你会慢慢理解它，最终以一种温和的方式融会贯通。

下面介绍构建方式，如果你完全看不懂，那就死盯着它，盯着盯着会豁然开朗的。

（建议手推。）

下面说构建方式。

主体思路是基数排序，先排前 $2^0$ 位，再顺次推出 $2^1,2^2,\dots,n$ 位。

代码中为了写起来方便用 $j$ 代表 $2^j$，在我叙述构建过程中仍使用 $2^j$ 以便于理解。

在构建的过程中有一些小细节：

• 这个后缀根本就没有 $2^j$ 长啊？
  • 认为后面全是 $0$（字典序最小）即可。
• 没排完的时候有两个相等的后缀咋办？
  • 这个是后缀数组构建代码冗长的主要原因之一，我们被迫认为这两个后缀的 $\text{rk}$ 暂时相等。
  • 也就是说，在构建的过程中，$\text{rk}$ 和 $\text{sa}$ 其实是两套系统，$\text{rk}$ 相等的那些后缀是暂时相等的，而 $\text{sa[i]}$ 取遍了 $\mathbb N\cap[1,n]$，那些混不清的后缀在 $\text{sa}$ 中就堆在一起。
  • 那么我们每次多扩展 $2^j$ 位，所做的其实是把那些暂时相等的后缀定一个顺序，已经确定大小关系的那些关系我们不改变。
  • 而我们每次确定顺序的方式，就是基数排序的方式，基数排序有定理：先对第二关键字排序，再对第一关键字稳定排序，所得到的排序结果就是对的。
  • 反映到我们的写法上来，就是说我们要先把第二关键字定一个顺序（运用上一轮的 $\text{sa}$），然后用第一关键字 $\text{rk}$ 排一下序求出新的 $\text{sa}$，再用旧的 $\text{rk}$ 检查检查新的后缀有没有产生新的大小关系，求出新的 $\text{rk}$。

代码（$n$ 是字符串长，$m$ 是字符集大小）：

void S() {
    F(i,1,m) bn[i]=0;
    F(i,1,n) bn[rk[i]]++;
    F(i,1,m) bn[i]=bn[i-1]+bn[i];
    UF(i,n,1) sa[bn[rk[t[i]]]--]=t[i];
}
int main() {
    cin>>s;n=s.size();
    s=' '+s;m=max(n,127);
    F(i,1,n) rk[i]=s[i],t[i]=i;S();
    for(int j=1;j<=n;j<<=1) {o=0;
        F(i,n-j+1,n) t[++o]=i;
        F(i,1,n) if(sa[i]-j>0) t[++o]=sa[i]-j;S();
        F(i,1,n) t[sa[i]]=t[sa[i-1]]+(rk[sa[i]]!=rk[sa[i-1]]||rk[sa[i]+j]!=rk[sa[i-1]+j]);
        F(i,1,n) rk[i]=t[i];
        if(rk[sa[n]]==n) break;
    } 
    for(int i=1,j=0,k;i<=n;h[rk[i]]=j,i++) 
    for(j&&--j,k=sa[rk[i]-1];s[i+j]==s[k+j];j++);
    return 0;
}

代码中的 S() 就是已知第二关键字排出来的顺序 $\text{t}[1,n]$ 和第一关键字 $\text{rk}[1,n]$，排序求出新的 $\text{sa}[1,n]$。

（$\text{t[i]}$ 类似于 $\text{sa[i]}$ 的定义，表示某个后缀 $\text{suf}_{\text{t}[i]}$ 的后半段（$s_{[\text{t}[i]+2^j,\text{t}[i]+2^{j+1})}$）大小排名是第 $i$ 名。）

求出 $\text{t}[1,n]$ 的方式很简单，那些没有后半段的起始点肯定是最小的，先加进去（$[n-2^j+1,n]$），然后利用上一轮的 $\text{sa}$ 由小到大把有后半段的元素加进去，枚举的是后半段，所以加进去的是 $\text{sa}[i]-2^j$。

接下来排序，排完序后求新的 $\text{rk}$，也很简单，暴力判前半段和后半段是否相等即可，不相等的话就把 $\text{rk}$ 真的增加 $1$。

---

你可以理解一会儿上面的部分，再来看求 $\text{h}[1,n]$ 的部分，这部分与上部分关联较小。

这里利用了一个性质：$\text{h[rk[}i\text{]]}\ge\text{h[rk[}i-1\text{]]}-1$。

用文字叙述的话就是： $\text{suf}_i$ 与它排完序后的前驱的 $\text{lcp}\ge$ $\text{suf}_{i-1}$ 与它排完序后的前驱的 $\text{lcp}-1$。

证明：$\text{suf}_{i-1}$ 去掉首字母（$\text{suf}_i$）和 $\text{suf}_{i-1}$ 排完序后的前驱去掉首字母（$\text{suf}_{\text{sa}[\text{rk}[i-1]-1]+1}$）显然大小顺序还是后者小于前者，且 $\text{lcp}$ 长度减小了 $1$。

所以 $\text{suf}_i$ 已经与一个比它小的串有了 $\text{h[rk[}i-1\text{]]}-1$ 的 $\text{lcp}$ 长度了，如果在二者之间还能插进一个串，那么 $\text{lcp}$ 长度显然不小于该长度，证毕。

所以求 $\text h[\text{rk}[i]]$ 仅需要每次由 $\text{h[rk[}i-1\text{]]}-1$ 暴力拓展而来即可。

需要注意的点

• 基数排序别忘了对 bn 求前缀和。
• 有多测时，需要清空字符串，这是因为我们构建 $\text{h}[1,n]$ 时利用了字符串后面都是 0 的特点。
• 有多测时，由于我们需要保证 $\forall i>n$ 的 $\text{rk}[i]=0$，如果你写的是 memcpy(rk,t,sizeof t);，那么你需要清空 $\text t[0,+\infty)$，如果你写的是 F(i,1,n) rk[i]=t[i]，那么你需要清空 $\text{rk}[0,+\infty)$，最稳妥的方式是这两个数组都清空，其他数组没有必要清空。

例题 + 顺带总结

如果你没有看懂构建过程，不要紧，这与下面并无联系。

把数组的定义放在旁边，你照样可以看懂接下来的推导过程。

你发现通常建完后缀数组之后这个题跟后缀数组关系就不大了，你应用的可能只是序列问题的一些解决办法。

由于个人原因，以下可能有口胡题，可能有原题但这里不给出题号。

静态 lcp

给出一个字符串 $s$，$q$ 次询问 $(i,j)$，每次你需要回答 $\text{suf}_i$ 和 $\text{suf}_j$ 的 $\text{lcp}$。

$n,q\le 10^6$。

上方的构建过程中其实隐晦地提到了这个定理，上面是这么说的：

如果在二者之间还能插进一个串，那么 $\text{lcp}$ 长度显然不小于该长度。

这个是人类大脑可以感受出来的，即若字符串 $a\le b\le c$，则 $\text{lcp}(a,c)\le\min(\text{lcp}(a,b),\text{lcp}(b,c))$。

但是！再用人类智慧稍稍感受一下，其实若 $a\le b\le c$，则 $\text{lcp}(a,c)=\min(\text{lcp}(a,b),\text{lcp}(b,c))$。

证明的话只需要分类讨论 $\text{lcp}(a,b)$ 与 $\text{lcp}(b,c)$ 哪个大即可。

那推广一下，若 $a\le b\le c\le d$，$\text{lcp}(a,d)$ 怎么求？

由上面的定理我们知道 $\text{lcp}(a,c)=\min(\text{lcp}(a,b),\text{lcp}(b,c))$，那我们把 $b$ 拿掉，只剩下 $a\le c\le d$，则由上面定理我们知道 $\text{lcp}(a,d)=\min(\text{lcp}(a,c),\text{lcp}(c,d))=\min\{\text{lcp}(a,b),\text{lcp}(b,c),\text{lcp}(c,d)\}$。

用类似的方式我们可以推导出若 $n$ 个串满足 $\forall i\in[2,n],a_{i-1}\le a_{i}$，则 $\text{lcp}(i,j)=\min\limits_{k=i+1}^{j}\text{lcp}(k-1,k)$。

直接应用到后缀数组上，则我们发现 $\text{lcp}(\text{suf}_i,\text{suf}_j)=\min\limits_{k=i+1}^{j}\text h[k]$。

于是这变成一个 $\text{RMQ}$ 问题。

小总结

这其实是相当重要的一部分，后缀数组的最主要作用就是可以方便快速的求任意两个子串的 $\text{lcp}$，之后的诸多问题都需要转化到求 $\text{lcp}$ 来解决。

来顺便做个例题：

P1117 [NOI2016] 优秀的拆分

给定一个字符串，问在所有的子串的所有拆分形式中，有多少是 $\text{AABB}$ 的形式，其中 $\text{A,B}$ 是任意非空字符串，同一子串的不同拆分方式算多种。

$n\le3\times 10^4$，多测 $10$ 组，实际单测可做 $n\le 5\times 10^5$。

看到字符串题第一反应是不要慌着套后缀数组后缀自动机，先想暴力做法。

话说这个题 $\Theta(n^2)$ 有 $95$ 分来着。

考虑每个合法答案一定是两个 $\text{AA}$ 串拼起来的，所以设 $a_i/b_i$ 为以 $i$ 开头/结尾的 $\text{AA}$ 串数量，则答案为：

$$\sum_{i=1}^{n-1}b_ia_{i+1}$$

简单的方法是暴力哈希枚举一个 $\text{A}$ 来判断，复杂度 $\Theta(n^2)$。

考虑优化。

首先枚举 $\text{len}_\text{A}=k$，把 $k$ 的倍数点成为关键点 $\text{}$，则每个 $\text{AA}$ 串一定过恰好两个关键点。

枚举这两个相邻关键点的位置，用 $\rm lcp$ 判断一下有几个 $\rm AA$ 串即可。

B LCS

给定两个串，求它们的最长公共子串。

$n_1,n_2\le 10^5$。

Ex：给定 $m$ 组串，第 $i$ 组串有 $n_i$ 个，求每组至少一个串出现过的最长字符串。

$m,\sum n_i\le 10^5$。

要不直接讲 Ex？

首先把串串拼起来（中间加上互不相同的分隔符）建后缀数组，则我们的目的是找到 $\max\limits_{(i,j)}\min\limits_{k=i+1}^j\text{h}[k]$，且保证 $\text{sa}[i,j]$ 中每组的串都至少出现过一次。

给两种思路：

• 考虑二分答案 $k$，则我们把所有 $\text h[i]< k$ 的位置断开，直接查询每个连续段中是否 $m$ 组的串都有即可。
• 考虑枚举结尾位置 $j$，则我们要查询能包含所有串且最靠后的位置来求 $\text{RMQ}$，使用小根堆和一个记录每个元素是否出现的桶即可。

C 本质不同子串数

给定一个字符串，统计其有多少本质不同的子串。

$n\le 10^6$。

想起了曾经懵懵懂懂学 $\text{SAM}$ 的时候，那时我还是个无忧无虑的孩子啊。

其实 $\text h[i]$ 可以理解成后缀树上的 $\text{len}[\text{fa}[i]]$，因为后缀树类似于虚树嘛，正好也映射了 $\text{RMQ}$ 问题与笛卡尔树 $\text{LCA}$ 问题的互相转化。

（虽然后缀树并不是笛卡尔树啦。）

上面的理解没什么用，我们看这道题后缀数组咋做。

子串，其实就是后缀的前缀，仔细动动脑子的话，$\text{len}[i]-\text{h}[\text{rk}[i]]$ 其实就是 $\text{suf}_i$ 这个后缀比那些比它小的后缀能提供的更多的子串数量。

理解一下的话，大概就是比它小的后缀跟它的 $\text{lcp}$ 都不会超过 $\text{h}[\text{rk}[i]]$，所以那之后的部分只要取到了就没有人会含有（当然比它大的后缀可能含有）。

那你就理解为一个增量构造，按照字典序大小依次加入每个后缀，加入一个后缀的贡献就是 $\text{len}[i]-\text{h}[\text{rk}[i]]$，所以答案即为 $\sum_i\text{len}[i]-\text{h}[\text{rk}[i]]$。

Ex：统计多个串的本质不同子串？

拼一起加分隔符就好了嘛。

P4248 [ANOI2013] 差异

原题题意可以转化为：给定一个字符串，求一个定值减去 $\sum_{(i,j)}\text{lcp}(\text{suf}_i,\text{suf}_j)$。

$n\le 10^6$。

你发现这个东西他建完后缀数组之后，其实就是序列所有区间的 $\min$ 的 $\sum$ 嘛。

这个东西是典题，单调栈即可。

D 最长子串

给定串串和 $k$，求出现了至少 $k$ 次的最长子串。

$n,k\le 10^6$。

一个子串出现了至少 $k$ 次意味着它是至少 $k$ 个后缀的前缀，这些后缀排完序之后肯定是挨着的，且这个条件充要。

我们又有两种做法：

• 滑动一个长为 $k-1$ 的窗口，求 $\text h[i]$ 在这些窗口的最小值（求 $\text{lcp}$），然后把得到的这些值取 $\max$。
• 二分答案，把不符合要求的地方断开，检查连续段长度即可。

Ex：能否对于每个 $k\in [1,n]$ 求出该答案？

采用方法 $1$，即我们要解决如下数据结构问题：求对于 $k\in [1,n]$，每个长为 $k$ 的区间的最小值的最大值。

我们用单调栈找出每个数作为最小值的区间长度有哪几种，区间取 $\max$ 即可。

E 最长子串2

给定一个串串，求一个最长的串 $t$，使得存在两个位置出现过 $t$，且这两次出现无重叠部分。

$n\le 10^6$。

利用上方的类似思路，二分答案 $m$，把 $\text{h}[i]< m$ 断开，则我们要求每个连续段内是否存在 $(i,j)$ 使得 $|\text{sa}[i]-\text{sa}[j]|\ge m$。

直接求每个连续段内 $\text{sa}[i]$ 的最大值和最小值即可。

Ex：给定一个串串和 $k$，求一个最长的串 $t$，使得存在 $k$ 个位置出现过 $t$，且这几次出现无重叠部分。

$n\le 10^6$。

照例断开，则我们要找每个连续段的 $\text{sa}[i]$ 构成的集合是否存在一个子集满足大小为 $k$ 且不存在两个数 $(i,j)$ 间满足 $|i-j|<m$。

我们把每个连续段的集合找出来，由小到大排序贪心选择即可。

复杂度 $\Theta(n\log^2 n)$，难以通过。

其实 $\Theta(n\log n)$ 也挺简单的，直接求出每个 $\text{sa}[i]$ 对应的连续段标号，然后顺着 $\text{sa}$ 序列扫一遍即可，当前是哪个连续段就处理哪个连续段。

F 变回文

给定串串，要求在末尾添加尽可能少的字符，使其成为一个回文串。

$n\le 5\times 10^5$。

其实这个问题等价于枚举回文中心然后求前缀和后缀的 $\text{lcp}$。

那就转化为 $\text{lcp}$ 问题了，去找 A。

什么你不会求一个前缀和一个后缀的 $\text{lcp}$？拼起来再建后缀数组啊！

P9482 [NOI2023] 字符串

给定一个字符串，$q$ 次询问，每次给出 $i,r$，求有多少 $l\in[1,r]$ 满足 $s_{[i,i+l-1]}<\text{rev}(s_{[i+l,i+2l-1]})$，其中 $\text{rev}(s)$ 表示 $s$ 左右翻转。

$n,q\le 10^5$。

首先把 $s_{[i,i+l-1]}<\text{rev}(s_{[i+l,i+2l-1]})$ 变成 $\text{Suf}_i<\text{Pre}_{i+2l-1}$，当然这样会有一些副作用，等会再说，先来解决这个新问题。

比较字典序我们自然想到后缀数组的 $\text{rk}$，于是我们把这个串翻转之后接到自己身上，但不能直接接，为了避免各种麻烦，中间要加上隔断，形如 $s-c_1-\text{rev}(s)-c_2$，其中 $c_1,c_2$ 不能在字符集内，且二者不能相等，为了避免 $\text{rev}(s)$ 错误参与到 $s$ 的比较中。

然后我们就可以愉快列式子，下标从 $1$ 开始的话则 $\text{Suf}_i<\text{Pre}_{i+2l-1}$ 应该写成 $\text{rk}_i<\text{rk}_{2n+3-i-2l}$，发现这就是一个二维数点，将询问按照 $\text{rk}_i$ 从大到小排序，用两棵树状数组分奇偶性询问即可。

然后就是看这个副作用，答案无疑会多统计一些部分，这些部分的 $s_{[i,i+l-1]}=\text{rev}(s_{[i+l,i+2l-1]})$ 但 $\text{Suf}_i<\text{Pre}_{i+2l-1}$，我们瞪大眼仔细看发现这描述了一个回文中心在 $[i+l-1,i+l]$ 的回文串，于是我们用 $\text{manacher}$ 求个回文半径先。

你发现求完回文半径之后，回文串两边的两个不相等的字符唯一决定了 $\text{Suf}_i$ 和 $\text{Pre}_{i+2l-1}$ 的大小关系，所以只需要回文串右边的字符比左边的小那么整个回文串都是被多统计的，应当减掉。

小细节：如果回文串顶到边界了怎么办？

根据我们上面的后缀数组构建规则，我们钦定整个字符串的最后有一个 $c_1$，最前面有一个 $c_2$，使用这个来比较即可。

这个数点问题需要寻找一个锚定物，直接从条件推到结果是很麻烦的，这里的锚定物找的就是左半边字符串是否合法。

设回文串是 $[i-l_i,i+l_i+1]$（$l_i$ 是回文半径），则我们把 $\forall x\in[i-l_i,i],[x,i]$ 都应当被统计到，建立关于 $l,r$ 的平面直角坐标系，你发现这是一条横线。

我们看原来的询问的左半边字符串，$\forall l\in[1,r],[i,i+l-1]$ 是询问范围，这在平面直角坐标系里是一条竖线，扫描线完事！

这个题 Alex_Wei 选了整个串作为锚定物，于是他之后进行了一系列的坐标变换把斜线变成直线，所以说选好锚定物很重要。