字符串

· · 算法·理论

\text{Aho-Corasick Automaton}

前言：

流程

总述：因为一个字符串的字串是它的一个前缀的后缀，所以我们开一个字典树维护前缀，再在字典树上开一个失配树维护后缀。

我们知道，KMP 自动机仅限单个字符串，那么对于多个字符串就需要 AC 自动机了，就像广义后缀自动机对于后缀自动机一样。下图是一张已经建好的图。

具体地，首先要建一棵 Trie。绿边便是 Trie 本来的边，而黄边是 fail 指针。fail 指针也叫失配指针，类似于 KMP 当中的 next 指针。注意到 fail 指针的含义就是连向它的最长后缀。

如何构建 fail 指针？首先我们应该知道，应该按照 bfs 的方式去处理，因为只有当深层较小的 fail 指针都处理完后，才能更新深度较大的 fail 指针。

结合 KMP 的思想（下文用 f 表示 fail 指针，t 表示字典树上的边），假设当前是状态 u 推 v=t[u][c]，那么如果 t[f[u]][c] 存在，那么 v 的 fail 指针便可以继承为 t[f[u]][c]；否则，根据定义，若 k=f[u]，不断令 k=f[k]，直到 t[k][c] 存在或者报告没有。

这种求 fail 指针的方法时间复杂度很玄学，是 c\sum|s|?，因为既无法给出卡掉的例子，也无法证明时间复杂度，所以只需理解即可。这种 AC 自动机是 NFA。

Trie 图

引出一种新概念。在 Trie 上，t[u][c] 仅表示一条真实存在的边，现在进行延伸，表示通过字符 c 到达的状态。

于是在 bfs 的基础上，一边求出 fail 指针，一边建立 Trie 图。那么 f[t[u][c]] 直接为 t[f[u]][c]，这是当 t[u][c] 存在的情况；否则 t[u][c]=t[f[u]][c]。

这样时间复杂度便是确定的 O(c\sum|s|)。Trie 图在很多题中都需要用到。

性质

由于 fail 指针由深连向浅，所以一定构成一棵树。既然是树，那么便有很多可发挥的空间。如，高斯消元求解树上随机游走、dfs 序建可持久化线段树等。

但是最常见的还是 dp。如果要求把一个字符串分成若干段，如果一段是给定字符串，那么就加上一个贡献；最后问最大贡献。这就是一个 AC 自动机上 dp 经典例题。如果每次暴力去跳 fail 的话，显然会超时，但是注意到跳的时候有很多无效状态（即不是某个串的末尾），这时候就要缩链，即确保每次跳都是有效的。可以证明这样复杂度极限是 O(n\sqrt n)。

当然，如果转移只跟当前状态有关，也可以建好图后直接求解。

\text{Palindromic Tree}

又称回文自动机（PAM）。

一个状态 u 表示一个回文子串 t_u，to[u][c] 表示在 t_u 两边加上 c 到达的状态，f[u] 既然是失配指针，则表示 t_u 的最长回文后缀。考虑怎么建出这个回文自动机。

流程

先建两个初始点 s0 和 s1，可以理解为 s0 长度为 0，s1 长度为 -1，那么 f[s0]=s1。记 p 为当前状态，l[u] 为 t_u 的长度。

令 q=p，对于字符 s_i，不断让 q 跳 fail 直到 s_i=s_{i-l[q]-1}，如果 v=to[q][s_i] 不存在则增加状态，该状态即为以 s_i 结尾的最长回文子串。显然 l[v]=l[q]+2。考虑求出 fail 指针，从 q 再往上跳，判定条件不变，找到 t_v 的最长回文子串，f[v]=to[q][s_i]。然后将 p 设为 v。

分析一下时间复杂度，分析 l 的变化情况，每次往上跳 l\to l-2，找到后最终 l\to l+2，容易发现全局最多跳 O(n) 次，所以是对的。以下是 abaa 的回文自动机。

性质

通过回文自动机的流程可以证明一个字符串本质不同的回文子串个数严格不超过 n，因为每次最多新增一个状态，而状态不会漏（因为更小的回文子串前面一定出现过）。

和 AC 自动机类似的，一些问题也可以转到 fail 树上求解。

\text{Suffix Array}

可以求出把一个字符串的所有后缀按字典序排序后，以 i 开始的后缀的排名 rk_i 以及排名为 i 的后缀的起始位置 sa_i。以下钦定字符串下标从 1 开始，长度为 n，s_i 表示 i 开头的后缀。

倍增法

规定 s_{n+1\sim 2n} 为负无穷，rk_{i,j} 表示 i\sim i+2^{j}-1 这段区间在长度为 2^j 当中的排名，sa_{i,j} 同理。

考虑利用倍增思想，在比较 rk_{i,j} 与 rk_{k,j} 的时候，本质上是先比较 rk_{i,j-1} 与 rk_{k,j-1}，然后再比较 rk_{i+2^{j-1},j-1} 与 rk_{k+2^{j-1},j-1}，于是执行 \log n 次双关键字排序便可做到 O(n\log^2 n)。考虑优化。

事实上 rk 的值域很小，所以可以考虑基数排序，先以第二关键字进行计数排序，再以第一关键字进行计数排序。这样时间复杂度是 O(n\log n)，但是常数很大。发现在以第二关键字进行排序时不需要进行计数排序，事实上等价于将 i>n-2^{j-1} 放到开头，其余按顺序即可，感性理解。

当然有 O(n) 的方法，但是并不常用。

容易发现 rk_{sa_i}=sa_{rk_i}=i。

height 数组

非常有用的东西，以下简写为 h。

> 定理：$h_{rk_i}\ge h_{rk_{i-1}}-1$。 > >考虑证明，不妨假设 $s_{i-1}=aAD$，那么 $s_i=AD$。假如 $aA$ 的长度为 $h_{rk_{i-1}}$，那么 $s_{sa_{rk_{i-1}-1}}=aAB$，并且有 $B<D$。于是显然存在一个后缀 $s_j$ 为 $AB$，那么有 $AB\le s_{sa_{rk_{i}-1}}<AD$，证毕。 于是便可以直接 $O(n)$ 求出 $h$ 了。 ## 性质 - 如果 $i<j$，则 $\text{lcp}(s_{sa_i},s_{sa_j})=\min\limits_{k=i+1}^{j}h_k$。感性理解即可。于是求任意两个后缀的 $\text{lcp}$ 便能用 st 表做到 $O(1)$。 - $S$ 本质不同的子串个数为 $\frac{n(n+1)}{2}-\sum\limits_{i=1}^{n}h_i$。 - 求第 $k$ 大子串可以通过二分的方式，找到第一个 $g_i=\sum\limits_{i=1}^{x}l_i-h_i\ge k$ 的位置，$l_i$ 表示 $s_{sa_i}$ 的长度，答案就是 $s_{sa_i,sa_i+k-g_{i-1}}$。 # $\text{Suffix AutoMaton}

下图分别是 abcbc 的 to 和 fail。

。

状态及 \text{endpos}

一个状态表示一个等价类，等价类是一个子串集合，里面所有字符串的 \text{endpose} 集合相同。对于子串 t，\text{endpose}(t) 为 t 在原串 s 中所有结束位置的集合。

定理一：假设 |t1|>|t2|，则 \text{endpos}(t1)=\text{endpos}(t2) 为 t2\in S(t1) 的充分条件，其中 S(t) 表示 t 的后缀集合。

推论一：假设 |t1|>|t2|，则要么 \text{endpos}(t1)\cap\text{endpos}(t2)=\varnothing，要么 \text{endpos}(t1)\subseteq \text{endpos}(t2)。且 t2\in S(t1) 是第二个式子成立的充要条件。

当 t2\not\in S(t1) 时，第一个式子显然成立。

先证充分性，如果 t2\in S(t1)，则 t1 每一次出现 t2 必定会出现，但 t2 出现时 t1 不一定出现。再证必要性，当 t2\not\in S(t1) 时，第二个式子不成立。

定理二：一个等价类中的所有子串长度排序后一定是连续的。

令 t 为该等价类中长度最长的子串，那么该等价类中的其他子串一定是它从前往后一段连续的后缀。

to 和 fail

to 边就是状态 u 的子串集合末尾增加 c 之后（必须还是一个子串）到的一个新的状态 v。v 可能还有从其他状态增加 c 之后的子串，所以 \text{len}(v)\ge \text{len}(u)+1，其中 \text{len}(u) 表示该等价类中最长子串的长度。

建出来的图显然是一个 DAG，并且任意一个子串都能被一条唯一路径表示。

由于 \text{endpos} 存在包含关系，所以联系到 fail 上去想。那么状态 u 的 fail 就可以定义为，令 t 为 u 中最长的子串，t' 是 t 最长的一个后缀且满足 \text{endpos}(t)\subsetneqq\text{endpos}(t')，则 u 的 fail 指向 t' 所在的等价类 v。

定理三： fail 形成一棵树。

定理四：令 v 是 u 的 fail，则 \text{len}(v)+1=\text{minlen}(u)。

因为 t' 是最长的满足条件的后缀了，所以它就是 v 中最长的子串。

推论二：从 u 跳 fail 直到根，若 p 在该路径上，则 [\text{minlen}(p),\text{len}(p)] 互不相交且并集为 [0,\text{len}(u)]。

相当于是连续若干段 t 的后缀。

流程

跟回文树的构造类似，用增量式构造。令 l 为 i-1 的状态。当前插入字符为 s_i。

插入 c 后肯定会新增一个状态 x，即 \text{endpose}=\{i\}，\text{len}(x)=\text{len}(l)+1，考虑更新 fail 和 to。

令 p=l，p 开始跳 fail，直到 to_{p,c} 存在，因为如果不存在，则应该在 x 这个等价类中。如果 p 一直跳到根都不满足条件，则说明 c 第一次出现，直接将 f_x 设成 rt 即可。

否则，令 q=to_{p,c}，如果 \text{len}(q)=\text{len}(p)+1，那很好，q 这个等价类在加了 c 之后 \text{endpos} 只会增加 i，所以直接 f_x=q 即可。

否则，说明 \text{len}(q)>\text{len}(p)+1，但是对于 q 中 \text{len}>\text{len}(p)+1 的子串显然 \text{endpos} 是不变的，而其他的子串要归到增加 i 之后的等价类里。所以这时候只能将 q 分裂，新增状态 y，表示增加 i 之后的等价类。\text{len}(y)=\text{len}(p)+1，根据定义显然有 f_y=f_q，f_x=f_{q}=y。对于 to 的变化，由于它们原本是一个等价类，所以 to_y 要复制 to_q。在增加 c 后，再从 p 跳 fail，对于 to_{p,c}=q 的需要改成 y，因为等价类变了。

广义后缀自动机

https://lglg.top/322224

https://www.luogu.com.cn/article/pm10t1pc

对于多个串构建 SAM。

常见有三种做法：

第一种和第二种都会出现讨论中的问题，会产生空节点。

应用

求本质不同的子串个数。

利用 fail 树的性质，答案为 \sum(\text{len}(i)-\text{len}(f_i))。

求位置/本质不同第 k 大子串。

因为找第 k 大，考虑确定每一位，从小到大枚举。则需要知道走一条边有多少种子串。拓扑图上算一下就行了。

多数后缀问题常常会建反串的 SAM，fail 树即为后缀树。如查询两个后缀的 lcp 即为后缀树上两个节点的 lca 的长度。