NOI 一轮复习 II：字符串

# NOI 一轮复习 II：字符串 ## 知识清单： - 概念与定义 - Trie 和有限状态自动机 - 字符串周期结构 - 字符串子串结构 - 回文串结构 - Lyndon 理论 ## 1. 概念与定义 在本文中我们默认字符集记为 $\Sigma$，字符串是由字符集中任意自然数个元素顺次拼接形成的序列，字符集 $\Sigma$ 生成的字符串集合记为 $\Sigma^*$，通常认为 $|\Sigma|$ 为常数。 对于字符串 $S$，令 $|S|$ 表示其长度，$S_i$ 表示其中第 $i$ 个字符（$i\in [1,|S|]$）。 - 定义空串是长度为 $0$ 的串，记为 $\epsilon$； - 两个串相等，当且仅当它们长度相等且对应位置字符相等； - 定义字符串的拼接操作：$R=S+T$ 是一个长度为 $|S|+|T|$ 的串，$R_i=S_i\ (i\in [1,|S|])$，$R_{i+|S|}=T_i\ (i\in [1,|T|])$，在无歧义的情况下也记为 $R=ST$（$S,T$ 也可以为单独字符），拼接操作具有结合律而没有交换律； - 可以发现，空串是满足对于任意串 $S$ 都有 $\epsilon+S=S$ 的串，同时满足这一条件的串也只有空串； - 定义串 $T$ 是串 $S$ 的子序列，当且仅当存在一组 $1\leq a_1<a_2<\ldots<a_m\leq |S|$，使得 $T=S_{a_1}S_{a_2}\ldots S_{a_m}$； - 定义串 $T$ 是串 $S$ 的反串，当且仅当 $|T|=|S|$，且 $T_i=S_{|S|-i+1}$，记为 $T=S^R$； - 定义串 $S$ 是回文串，当且仅当 $S=S^R$，将其最中间的字符（或最中间两个字符之间的位置）称为回文中心； - 定义串 $T$ 是串 $S$ 的前缀，当且仅当 $|T|\leq |S|$ 且 $T_i=S_i$，记为 $T=S[1\ldots |T|]$，无歧义时也记为 $Pre(|T|)$，不等于原串的前缀称为真前缀； - 定义串 $T$ 是串 $S$ 的后缀，当且仅当 $T^R$ 是 $S^R$ 的前缀，记为 $T=S[|S|-|T|+1\ldots |S|]$，无歧义时也记为 $Suf(|T|)$，不等于原串的后缀称为真后缀； - 定义串 $T$ 是串 $S$ 的子串，当且仅当存在 $a,b$ 使得 $S[1\ldots a]+T+S[b\ldots |S|]=S$，记为 $T=S[a+1\ldots b-1]$，特别地，当 $b=a+1$ 时有 $S[i\ldots i-1]$ 为空串，而如果 $l>r+1$，则 $S[l\ldots r]$ 没有意义，不等于原串的子串称为真子串； - 对于串 $S,T$，定义 $T<S$ 或 $T$ 的字典序比 $S$ 小，当且仅当 $T$ 是 $S$ 的真前缀或存在 $i\leq \min(|T|,|S|)$ 使得 $\forall j<i,\ T_j=S_j$，而 $T_i<S_i$。 --- ## 3. 字符串周期结构 本节前进行如下补充定义： - 定义**正整数** $p$ 是串 $S$ 的周期，当且仅当 $p\leq |S|$ 且 $S_i=S_{i+p}\ (i\in [1,|S|-p])$，如果 $p$ 还整除 $|S|$ 则称其为整周期； - 定义串 $T$ 是串 $S$ 的 Border，当且仅当 $T$ 是 $S$ 的前缀且 $T$ 是 $S$ 的后缀，**但 $T\ne S$**，为了方便也称 $|T|$ 是 $S$ 的 Border； 每个字符串 $S$ 都存在一个平凡周期：$|S|$，以及一个平凡 Border：$0$（或 $\epsilon$）。 ### 单串 Border 结构 关于周期和 Border 有如下浅显结论： **结论：$p$ 是 $S$ 的周期，当且仅当 $|S|-p$ 是 $S$ 的 Border。** 证明：$p$ 是 $S$ 的周期等价于 $S_i=S_{i+p}$ 对所有 $i\leq |S|-p$ 成立，也就等价于 $S[1\ldots |S|-p]=S[p+1\ldots |S|]$，也就等价于 $|S|-p$ 是 $S$ 的 Border。 接下来我们尝试分析一个串所有周期（或 Border）之间的关系和结构。 --- **弱周期引理（Weak Periodicity Lemma）：若 $p,q$ 是串 $S$ 的周期，且 $p+q\leq |S|$，那么 $\gcd(p,q)$ 也是 $S$ 的周期。** 证明：不妨设 $p<q$（$p=q$ 显然成立）。 对于 $i>q$，有 $S_i=S_{i-q}=S_{i-q+p}$； 对于 $q-p< i\leq q$，$i+p\leq |S|$，所以有 $S_i=S_{i+p}=S_{i-q+p}$。 因此 $\forall i\in [q-p+1,|S|]$ 有 $S_i=S_{i-q+p}$，这意味着 $q-p$ 是 $S$ 的周期。 而 $(q-p)+p\leq |S|$，同上可以继续减，由此模拟欧几里得算法过程，即可以得到 $\gcd(p,q)$ 是 $S$ 的周期。 --- 然而 $p+q\leq |S|$ 这个界虽然在一般分析中已经够用，但我们还可以加强上述引理： **周期引理（Periodicity Lemma）：若 $p,q$ 是串 $S$ 的周期，且 $p+q-\gcd(p,q)\leq |S|$，那么 $\gcd(p,q)$ 也是 $S$ 的周期。** 证明：参考叉姐的知乎文章 [https://zhuanlan.zhihu.com/p/85169630](https://zhuanlan.zhihu.com/p/85169630)，将其翻译和理解了一下。 这可能不是一种直观证明，但是我并不会直观的证明。 在这里为了方便，设 $|S|=n$ 并且 $S$ 的下标从 $0$ 开始，即 $S=S_0S_1\ldots S_{n-1}$，同时将 $S_i$ 映射为 $1\ldots n$ 之间的一个整数（使得不同字符映射到的整数不同）。 我们设 $s_p(i)=S_{i\bmod p}$，同样 $s_q(i)=S_{i\bmod q}$，我们设它们的生成函数分别为 $F_p(x)$ 和 $F_q(x)$。 根据它们的定义形式，它们应当是周期的，符号化： $$ F_p(x)=\dfrac{G_p(x)}{1-x^p},\ F_q(x)=\dfrac{G_q(x)}{1-x^q} $$ 其中 $G_p(x),G_q(x)$ 是次数分别不超过 $p-1,q-1$ 的多项式。 下面考虑求： $$ F_p(x)-F_q(x)=\dfrac{(1-x^q)G_p(x)-(1-x^p)G_q(x)}{(1-x^p)(1-x^q)} \\ =\dfrac{1-x^{\gcd(p,q)}}{(1-x^p)(1-x^q)}(\dfrac{1-x^q}{1-x^{\gcd(p,q)}}G_p(x)-\dfrac{1-x^p}{1-x^{\gcd(p,q)}}G_q(x)) $$ 注意第二步转化是提取了 $1-x^p$ 和 $1-x^q$ 的公约式 $1-x^{\gcd(p,q)}$。 熟知地，$\dfrac{1-x^q}{1-x^{\gcd(p,q)}}=\sum\limits_{i=0}^{q/\gcd(p,q)-1}x^{i\gcd(p,q)}$，这是一个 $q-\gcd(p,q)$ 次多项式，因此它乘上 $G_p(x)$ 的次数不超过 $p+q-\gcd(p,q)-1$ 次。 同理后一项，那么设括号里的整体为： $$ H(x)=\dfrac{1-x^q}{1-x^{\gcd(p,q)}}G_p(x)-\dfrac{1-x^p}{1-x^{\gcd(p,q)}}G_q(x) $$ 那么 $H(x)$ 是一个不超过 $p+q-\gcd(p,q)-1$ 次多项式。 由于 $F_p(x)\equiv F_q(x)\bmod x^n$（这是因为它们对应项系数就等于原串中某个字符），对比系数，从低次项开始归纳得 $H(x)\equiv 0\bmod x^n$（这一步的依据是 $H(x)$ 乘的那个幂级数的常数项显然为 $1$），而其次数 $p+q-\gcd(p,q)-1<n$，所以 $H(x)=0$，即我们得到了 $F_p(x)=F_q(x)$。 那么，根据裴蜀定理，设 $up+vq=\gcd(p,q)$，其中 $u>0$，那么我们对于任意 $i\in [0,n-\gcd(p,q)-1]$ 都有 $F_p(i)=F_p(i+up)=F_q(i+up)=F_q(i+up-vq)=F_q(i+\gcd(p,q))=F_p(i+\gcd(p,q))$，因此 $\gcd(p,q)$ 是 $S$ 的一个周期，得证。 --- 根据弱周期引理，对于任意长度不超过串长一半的周期 $p,q$，都有 $\gcd(p,q)$ 也是周期，所以： **短周期结构：字符串 $S$ 的所有不超过 $\dfrac{S}{2}$ 的周期都是其最短周期的倍数。** 根据 Border 与周期的关系，同时有： **长 Border 结构：字符串 $S$ 的所有不小于 $\dfrac{S}{2}$ 的 Border 构成等差数列，且如果排序后延申这个数列，下一项就是 $|S|$。** 接下来考察 $S$ 的所有周期与 Border 的结构： 首先我们有一个浅显的结论，若 $p,q$ 同为 $S$ 的 Border 且 $p<q$，那么 $p$ 也是 $S[1\ldots q]$ 的 Border，画个图容易理解。 设 $S$ 的最长 Border 长度为 $b_0$（也可以直接设为 $n$），那么长度不小于 $\dfrac{b_0}{2}$ 的 Border 和 $b_0$ 共同构成一个等差数列。 接下来设最长的小于 $\dfrac{b_0}{2}$ 的 Border 为 $b_1$，同理长度在 $[\dfrac{b_1}{2},b_1]$ 间的 Border 构成一个等差数列。 以此递推，$b_i<\dfrac{b_{i-1}}{2}$，因此总共形成了 $O(\log n)$ 个等差数列，所以有： **字符串的周期/Border 结构：字符串 $S$ 的所有周期或 Border 形成了 $O(\log n)$ 个值域不交的等差数列。** --- > 例题 $1$：[WC 2016] 论战捆竹竿 > > 给定字符串 $S$，问 $S$ 的所有周期的线性组合（系数为正整数）可以表示出多少个 $[1,w]$ 内的数。 > > $O(n\log n+\log w)$。 将 $S$ 的所有周期拆为 $O(\log n)$ 个等差数列，先考虑其中某一个等差数列中的数的线性组合。 考虑同余最短路，设此等差数列首项为 $x$，公差为 $d$，项数为 $m$，在 $\bmod x$ 意义下考虑，从 $i$ 向 $i+kd\ (d\in [0,m))$ 连边，从超级源点向初始数列中所有点连边，最短路即为每个余数的最小可能表示的数。 考虑优化转移，根据这种特殊连边规律，整个图将分为 $\gcd(x,d)$ 个长度为 $\dfrac{x}{\gcd(x,d)}$ 的圈，对于每个圈我们只需要从其最短路最小的点出发，进行一圈的更新即可，考虑到项数的限制，可以用单调队列维护决策。 再解决多个等差数列并的问题，其实我们只需要实现换模数即可，设原来的模数为 $m1$，最短路数组为 $dis1$，新模数为 $m2$，最短路数组为 $dis2$，设 $i\in [0,m1)$，那么显然可以用 $dis1_i$ 更新 $dis2_{dis1_i\bmod m2}$，还可以用 $dis1_i+k\times m1$ 更新 $dis2_{(dis1_i+k\times m1)\bmod m2}$，可以发现这又是一个类似最短路的过程，然而这个结构比较简单，我们只需要先进行 $dis1_i$ 的转移后再对于每个圈扫描一次，进行形如 $dis1_i+m1$ 的转移即可，因为是一个环，所以转两圈就可以保证覆盖到了所有转移。 求所有 Border 需要用到下面介绍的 KMP 算法或其他方法。 时间复杂度为 $O(n\log n+\log w)$。 --- ### 前缀 Border 结构 接下来讨论串 $S$ 的所有前缀的 Border 间的关系。 令 $B_i$ 表示 $Pre(i)$ 的最长 Border 长度，$\textbf{Bd}_i$ 表示 $Pre(i)$ 的 Border 长度集合。 **命题：$\textbf{Bd}_i=\begin{cases} \{0\}\qquad\qquad\qquad (B_i=0) \\ \textbf{Bd}_{B_i}\cup \{B_i\}\qquad (B_i>0)\end{cases}$。** 证明：$Pre(i)$ 的小于 $B_i$ 的 Border 都是 $Pre(B_i)$ 的 Border，而 $B_i$ 是最大的，因此其余的 Border 都在 $\textbf{Bd}_{B_i}$ 中。 因此我们只需要求出所有 $B_i$，就可以得到字符串所有前缀的 Border 关系。 接下来介绍的 KMP 算法可以在线性时间内求出所有 $B_i$： 考察 $Pre(i)$ 和 $Pre(i-1)$ 的 Border 之间的关系，容易发现：如果 $x$ 是 $Pre(i)$ 的一个非空 Border，那么 $x-1$ 就是 $Pre(i-1)$ 的 Border，这是因为我们可以由 $S[1\ldots x]=S[i-x+1\ldots i]$ 得到 $S[1\ldots x-1]=S[i-x+1\ldots i-1]$。 也就是说，$B_i$ 如果非零，则 $B_i-1$ 必然是 $Pre(i-1)$ 的 Border。 由此，KMP 算法过程如下： - 顺序扫描 $i\in [1,n]$，维护 $B_{i}$； - 当 $i$ 变为 $i+1$ 时，先令 $j=B_i$，随后只要 $j>0$ 且 $S_{j+1}\ne S_{i+1}$，就令 $j\leftarrow B_j$； - 若 $j>0$ 或 $j=0$ 但 $S_1=S_{i+1}$，则 $B_{i+1}=j+1$，否则 $B_{i+1}=0$。 第二步即从大到小枚举 $Pre(i)$ 的所有 Border，尝试找到一个后继为 $S_{i+1}$ 的 Border，以此生成一个 $i+1$ 的最长 Border，这是一个暴力的思想。 但是这样的复杂度是正确的，考虑 $B_i$ 的移动，上面算法中的 $j$ 至多增加了 $n$ 次，而每次减少后仍为非负数，因此增加和减少的次数都是 $O(n)$，所以整个算法的时间复杂度为 $O(n)$。 事实上，根据前面的命题，我们就可以归纳出 $S$ 的所有前缀的 Border 结构： **定义：建立一棵 $n+1$ 个结点的图，编号为 $0,\ldots,n$，对于 $i\ge 1$ 从 $i$ 向 $B_i$ 连边，这构成了一棵树，称为失配树或 Fail 树，将 $B_i$ 称为 $i$ 的失配指针。** 那么，一个前缀 $Pre(i)$ 的所有 Border 即它在失配树上的所有祖先。 --- > 例题 $2$：[NOI 2014] 动物园 > > 给定字符串 $S$，你需要对于所有 $S[1\ldots i]$ 求出其长度不超过 $\dfrac{i}{2}$ 的 Border 数量。 构建出 $S$ 的失配树，我们只需对每个 $i$ 求出 $Pre(i)$ 的最长的不超过 $\dfrac{i}{2}$ 的 Border 即可，则其深度（可能需要减 $1$）即为所求。 考虑模仿 KMP 算法的过程，我们发现仍然可以用一个变量 $j$ 维护当前的 $i$ 对应的最长的不超过 $\dfrac{i}{2}$ 的 Border，可以发现，我们依然有性质：$Pre(i+1)$ 的最长的不超过 $\dfrac{i+1}{2}$ 的 Border 减去 $1$ 是 $Pre(i)$ 的一个不超过 $\dfrac{i}{2}$ 的 Border，因此维护的方法和 KMP 算法基本相同。 时间复杂度为 $O(n)$。 --- ### Aho-Corasick 自动机 下面我们考虑用失配树来解决**字符串匹配问题**。 在一般的字符串匹配问题中，我们给定若干个串 $T_1,\ldots,T_m$，称为模式串（Pattern），再给定若干个串 $S_1,\ldots S_n$，称为文本串（Text），我们需要统计 $T_i$ 在 $S_j$ 中作为子串的出现情况。 先讨论最简单的情形，即 $n=m=1$： **一对一匹配：给定模式 $T$ 和文本 $S$，求 $T$ 在 $S$ 中作为子串出现的所有位置。** 实际上，这个问题和求前缀 Border 问题几乎是相同的，下面给出一种比较直观的理解： 考虑将 $T$ 和 $S$ 连接，中间加上一个分隔符 $\Delta$，构成串 $T\Delta S$，求其所有长度大于 $|T|$ 的前缀的 Border，但我们要求这个 Border 的长度不能超过 $|T|$，那么求出的是什么呢？实际上是对于 $S$ 的每一个前缀，求出其后缀与 $T$ 的前缀的最长匹配长度，当这个值恰好等于 $|T|$ 时，我们就找到了 $T$ 在 $S$ 中的一次出现。 因此，我们直接复用 KMP 算法就可以解决这个问题，实现上并不用把它们连接起来，只需要基本仿照原先的 KMP 过程，首先预处理 $T$ 每个前缀的失配指针，然后维护当前 $S$ 前缀和 $T$ 的最长“Border”，从前缀 $i$ 到 $i+1$ 时只要不断跳失配指针，直到找到了一个和 $S_{i+1}$ 相等的后继。 接下来我们考虑这种做法的本质：不论是在求前缀 Border 时“自匹配”，还是模式串与文本串的一对一匹配，中间的一个核心过程都是根据当前指针和下一个“目标字符”（$S_{i+1}$），找出当前指针的一个最长的 Border 使得其后继等于这个目标字符。 令当前指针为 $x$，目标字符为 $c$，将 $x$ 不断跳失配指针直至找到一个后继为 $c$ 的 Border，令这个 Border 添上 $c$ 后位于的指针为 $t(x,c)$。 设字符串为 $S$，仍然令 $i$ 的失配指针为 $B_i$，下面考虑如何维护 $t(x,c)$。 **命题：$t(x,c)=\begin{cases}x+1\qquad\quad (S_{x+1}=c) \\ t(B_x,c)\qquad (S_{x+1}\ne c)\end{cases}$。** 证明：只要考虑我们在 KMP 过程中的操作即可，要么直接从 $x$ 到 $x+1$，要么就要先跳一次失配指针再说。 又 $t(0,c)=0\ (S_1\ne c)$，所以我们得到了一种 $O(|S|\times |\Sigma|)$ 构造 $t(x,c)$ 数组的方法。 对 $T$ 构建这个数组，而利用这个数组，我们只需不断按照它的指示依次走 $S$ 中的每个字符，只要走到了 $|T|$ 就找到了 $T$ 在 $S$ 中的一次出现，同时我们还可以通过中间每一步的结果知道 $S$ 的每个前缀的后缀与 $T$ 的前缀的最长匹配。 如果将 $0$ 设为出发点，从 $x$ 到 $t(x,c)$ 建立转移，当我们钦定一个或一些终点 $E$ 时，这就构成了一个**确定性有限状态自动机**，而它可以接受的所有字符串，就是其后缀与 $T$ 的前缀能匹配的最大长度属于 $E$ 中终点的那些字符串，特别地，如果 $E$ 只包含 $|T|$ 一个点，那么它可以接受的字符串就是以 $T$ 为后缀的所有串。 下面我们将一对一的匹配问题扩展： **多对一匹配：给定 $m$ 个模式串 $T_1,\ldots,T_m$ 和一个文本串 $S$，求每个 $T_i$ 在 $S$ 中的出现次数。** 我们将上面的理论进行扩展，具体地，首先建立出 $T_1,\ldots,T_m$ 构成的一棵字典树 $TR$。 令字典树上以 $x$ 为父亲的字符为 $c$ 的边对应的 $x$ 的子结点为 $ch(x,c)$，以及 $B_x$ 表示 $x$ 的失配指针（$x,B_x$ 都是 $TR$ 上的结点），和 $t(x,c)$ 定义同上。 容易解决的是：$t(x,c)=\begin{cases}ch(x,c)\qquad (\exists y=ch(x,c)) \\ t(B_x,c)\qquad (\text{otherwise})\end{cases}$，理由和上面一样，但是我们如何求出 $B_x$ 呢？ 同样思考 KMP 算法的过程，对于 $B_x$，我们首先从 $x$ 的父结点 $fa_x$ 的失配指针开始不断继续跳失配指针，直到存在后继等于 $fa_x$ 到 $x$ 的这条边上的字符，所以 $B_x=t(B_{fa_x},c)$，其中 $c$ 是 $fa_x$ 到 $x$ 的边上字符。 由此构建出的自动机被称为 **Aho-Corasick 自动机**，简称 **AC 自动机**，通常我们不强调其终点集合，而主要强调其结构。 下面整理一下 AC 自动机的生成过程： - 首先建立一棵包含所有模式串的字典树 $TR$； - 对 $TR$ 从根开始进行一次 BFS，在一个点处枚举所有后继字符，按照上面的规则计算 $t(x,c)$，对于其子结点，按照上面的规则计算失配指针。 - 最终我们计算出所有点的失配指针和转移，AC 自动机建立完毕。 此过程复杂度为 $O(\sum|T|+|TR|\times |\Sigma|)$。 **注意：AC 自动机中包含了两棵树，一棵是 Trie 树，还有一棵是失配树，它们是不同的。** 接下来使用 AC 自动机解决多对一匹配： 建立模式串的 AC 自动机，从起始点开始依次按照文本串中字符进行转移，每转移一个字符，就给当前到达的结点的标记增加 $1$，表示**当前结点在失配树上的所有祖先的出现次数增加了 $1$。** 最后我们对失配树进行一次 DFS，统计子树和，就得到了每个模式串的出现次数。 匹配过程的复杂度是 $O(|S|)$，最终统计的复杂度是 $O(|TR|)$。 由此，**多对多匹配问题**也可以解决了，只要对每个文本串都进行一次上述匹配过程，最后 DFS 统计即可。 整个算法的复杂度是 $O(|TR|\times |\Sigma|+\sum|T|+\sum|S|)$。 现在看上去比较碍眼的就只有乘的那个 $|\Sigma|$ 了，当字符集较大时，有没有可能把这部分的复杂度降下去呢？ 想要解决这个问题，我们需要用某种数据结构维护 $t(x,c)$，可以发现 $t(x,c)$ 相对于 $t(B_x,c)$ 差别并不大，我们用**可持久化线段树**来对此维护，具体地，我们对每个点 $x$ 用线段树维护 $t(x,c)$，这棵树只是在 $B_x$ 那颗树的基础上修改了 $x$ 所有连向儿子的那些边对应的字符的位置。 如果采用这个优化，整个多对多匹配的复杂度变为 $O((|TR|+\sum |S|)\log |\Sigma|+\sum |T|)$。 --- > 例题 $3$：[NOI 2011] 阿狸的打字机 > > 给定一个包含字符和操作 $\text{B,P}$ 的长为 $n$ 的操作序列，用于生成一个 Trie，顺序扫描这个序列，维护一个当前串，遇到字符就加到当前串末尾，遇到 $\text{P}$ 就将当前串加入 Trie，遇到 $\text{B}$ 就将当前串末尾字符删除。 > > 接下来有 $m$ 次询问，每次给定 $x,y$，问第 $x$ 个加入 Trie 的串在第 $y$ 个中作为子串出现多少次。 > > $|\Sigma|=26$ 视为常数。 时刻维护当前串在 Trie 上的位置，每次要么移动到儿子，要么移动到父亲，要么保持不变，因此 Trie 的总点数和建 Trie 复杂度都是 $O(n)$ 的。 然后建立 AC 自动机，接下来考虑询问的实质： 询问第 $x$ 个串 $S_x$ 在第 $y$ 个串 $S_y$ 中的出现次数，也就是求有多少个 $S_y[1\ldots i]$ 的一个后缀等于 $S_x$， 或者说 $S_y[1\ldots i]$ 在 AC 自动机上走完之后来到了 $S_x$ 在失配树上的子树中。 而 $S_y[1\ldots i]$ 就是字典树上 $S_y$ 对应的点到根结点的链，所以我们要问的就是：一个点在一棵树上的祖先链中属于另一个点在另一棵树上子树的点数。 这是个数据结构问题，具体不多赘述，我们离线询问，对 Trie 进行 DFS，可以以总共 $O(|TR|)$ 次操作时刻维护当前点所有祖先的贡献，而选取的数据结构可以是树状数组，因为失配树的子树求和在 DFS 序上即是区间求和。 时间复杂度为 $O((|TR|+m)\log |TR|)$。 --- > 例题 $4$：[POI 2000] 病毒 > > 给定字符串集 $\{S_1,\ldots,S_n\}$，求是否对于任意正整数 $m$ 都存在长度为 $m$ 的串 $T$，使得任何 $S_i$ 都不是它的子串。 > > $|\Sigma|=2$ 视为常数。 首先构建 $S_1,\ldots,S_n$ 的 AC 自动机，接下来我们转化问题，将所有 $S_i$ 对应的点的子树（失配树中）中所有点打上标记，表示不能经过这些点，最后，我们就是要找到一条无限长的路径，不经过任何打上标记的点。 我们可以将未打上标记的点和它们之间的边拿出来，进行一次缩点，如果从起点出发能够到达的是一个 DAG，那么不存在这样的路径，否则只要走到一个大小不小于 $2$ 的强连通分量，就可以构造出一个无限长的路径。 时间复杂度为 $O(\sum |S_i|)$。 这题的题解区流行一种 DFS 的方法，其中一部分是一个点只访问一次的，另一部分是每次都搜的，对于前者我不清楚其正确性，对于后者我不清楚其复杂度，所以这里没有采用 DFS 方法。 --- ## 4. 字符串子串结构 下面我们讨论一个字符串 $S$ 的所有子串形成的结构。 通常来说，刻画 $S$ 子串结构的主要方式有：**后缀数组，后缀自动机，后缀树。** 在本节中，我们将详细介绍三者的原理和三种独特的构造方法（**不会介绍后缀数组的单独线性构造**），并且指出它们之间的内在联系。 其中最容易理解的是**后缀树**，下面就从后缀树开始说起。 --- ### 后缀树的构建 对于串 $S$，将 $S$ 的所有后缀插入一棵字典树，将这个字典树叫做 $S$ 的**后缀字典树**。 我们将后缀字典树上所有**不对应 $S$ 的任何后缀且恰有一个儿子**的非根节点称为**二度点**。 现在我们考虑将这个后缀字典树进行如下压缩： - 原本后缀字典树中每条边上带有一个字符，压缩后每条边上带有一个字符串； - 压缩过程：每次找出一个二度点，将它的父亲与儿子连接，边上的字符串是它的父亲到它的字符串拼上它到它儿子的字符串，然后删除这个二度点。 将这样得到的树称为**后缀树（Suffix Tree，ST）**，树上的一个点称为一个**等价类**或 $\text{Startpos}$ 等价类。 - 称一个串 $T$ 属于一个等价类 $s$，当且仅当从后缀树的根结点出发，每次走 $T$ 的一个前缀对应的边，最终走到了 $s$ 父亲到 $s$ 之间的边上的某个位置。 - 等价类 $s$ 的代表元是属于 $s$ 的所有串中最长者，事实上这也就是等价类对应的那个后缀树上的点在原后缀字典树上对应的子串。 后缀树的另一种理解： - 将后缀字典树上所有 $S$ 后缀对应的点称为关键点，后缀树是关键点连同根结点的虚树。 根据构造过程，我们可以得到关于后缀树的如下性质： **性质 $1$：每个 $S$ 的子串都属于恰好一个等价类，同时属于任何一个等价类的也一定是 $S$ 的子串。** 证明：每个子串肯定都对应后缀字典树上一个点，而压缩操作只是将所有二度点压到了边上，所以每个子串还是恰好在一条边上；而属于一个等价类的必定也是后缀字典树对应的一个点，即子串。 **性质 $2$：每个 $S$ 的后缀都是一个等价类的代表元。** 证明：根据定义，$S$ 的一个后缀对应的后缀字典树上的点必定不是二度点，不会被缩，所以它是一个后缀树上的点对应的串，即其等价类的代表元。 **性质 $3$：后缀树的叶结点的代表元是 $S$ 的后缀。** 证明：假设不是，那么在后缀字典树上，这个结点应该是在插入某个后缀时的中间结点，下面必然有子结点。 **性质 $4$：后缀树的结点数量不超过 $2|S|$。** 证明：除根结点和对应后缀的点外，其他点至少有两个儿子，因此其数量小于非空后缀数量，再加上非空后缀和结点，就是 $2|S|$。 形如 $\text{aa}\ldots \text{ab}$ 的串可以达到 $2|S|-1$ 个结点，而稍加精细讨论可以知道 $2|S|$ 个结点只有 $|S|=1$ 时才能达到。 接下来我们来讨论等价类的性质。 **定义：一个串 $T$ 在 $S$ 中作为子串的所有出现，其左端点集合记为 $\text{Startpos}(T)$，其右端点集合记为 $\text{Endpos}(T)$。** 那么等价类就满足： **定理：两个子串属于同一等价类，当且仅当它们的 $\text{Startpos}$ 集合相同。** 证明：从后缀字典树的角度考虑，$\text{Startpos}$ 的含义是它是哪些后缀的前缀，也即它在后缀字典树的子树中包含的后缀集合。 继续从虚树的角度考虑问题，两个串属于同一等价类，等价于它们对应的后缀字典树的结点被缩到了后缀树上的同一条边，由于后缀树保留了所有后缀，这也代表了它们子树中的后缀集合相同，即 $\text{Startpos}$ 集合相同。 反之亦然，如果两个子串属于不同等价类，那么它们对应的后缀树上的点要么是祖先关系，要么是平行关系，那么对应的 $\text{Startpos}$ 关系就是包含或不交。 有了这一视角，下面再给出一些关于后缀树和等价类的性质： **性质 $5$：两个等价类对应的 $\text{Startpos}$ 集合或者有包含关系，或者交为空。** 证明：上面定理的证明过程已经说明了这一点。 **性质 $6$：$\text{Startpos}$ 集合相同的若干子串，它们的长度构成公差为 $1$ 的等差数列，且短的串是长的串的前缀。** 证明：这些子串构成一个等价类，等价类对应了后缀字典树上一段祖先链，自然满足这些条件。 有了上面这些基础，我们现在可以用后缀树的视角来归纳字符串的子串结构： **字符串子串结构：字符串 $S$ 的所有子串根据其出现位置的左端点集合可以被划分成 $O(|S|)$ 个等价类，任何两个等价类对应的集合包含或不交，因此这形成了被称为后缀树的树形结构。** 因此，从逻辑上，后缀树上的祖先关系指的其实是两个等价类对应 $\text{Startpos}$ 的包含关系。 上面我们讨论了一个串子串的情况，这里也讨论一下多串情况。 给定字符串集合 $S_1,\ldots S_n$，我们可以用类似方法刻画它们的子串的并集的结构，只需要将每个串的每个后缀都插入后缀字典树，再据此建立后缀树即可，这样的后缀树称为**广义后缀树**。 --- 接下来我们介绍如何构建一个串的后缀树。 下面介绍的 **Ukkonen 算法**可以在线性时间内构造给定字符串的后缀树。 Ukkonen 算法是从前往后增量构造当前前缀的**后缀树局部**。 这里有必要阐明所谓“后缀树局部”和后缀树的差别，在后缀树中我们保留的所有后缀对应的点，即使它们只有一个儿子，但是在这里的后缀树局部中，我们**不保留**这些点（因为它们后续可能就不是后缀了）。 考虑在最后加入一个字符产生的影响： - 每一个原先的后缀都会在后面新增上这个字符（注意包括空后缀）。 而原先的后缀在后缀树上有两种表现形式：叶子和非叶子。 对于叶子，可以在它的父亲到它的边上直接追加这个新字符，我们称此为**自然延续**。 而对于非叶子，由于它可能并没有被剥离出一个单独的结点，所以我们无法延续，那么如果一定要构造出这个后缀，就需要**拆点**。 如图，原先一条边上字符串为 $\text{abc}$，现在有后缀 $\ldots\text{abd}$，那么就需要在 $\text{b,c}$ 之间分开，中间新增一个点，连出一条 $\text{d}$ 边：  那么，哪些后缀是无法自然延续的呢？事实上，设当前插入了前缀 $Pre(x)$，那么若后缀 $S[y\ldots x]$ 不是叶子，则 $S[y+1\ldots x]$ 也必不是叶子（前者所有子结点在后者也有对应的转移），所以这些无法自然延续的后缀就是所有长度不超过 $l$ 的后缀。 更本质地说，这个长为 $l$ 的后缀是当前最长的在 $Pre(x)$ 中出现次数大于 $1$ 次的后缀，称为最长隐后缀。 在 Ukkonen 算法的过程中，我们始终维护当前的这个 $l$，当插入一个末尾新字符 $c$ 时： - 对于当前的 $l$，如果 $l$ 对应的后缀树上的位置存在下一个字符为 $c$ 的转移，那么加 $c$ 之后的后缀还是在之前出现过，所以 $l$ 保持不变，同时我们也无从拆点（例如上图中原本的 $\text{abc}$ 边加上了一个后缀 $\ldots \text{abc}$，那么无法拆出一条新边和一个新点）； - 如果不存在下一个字符为 $c$ 的转移，那么我们就如上图进行拆点，同时令 $l$ 减小 $1$（因为当前的 $l$ 已经成为叶子了）。 直接暴力进行这个过程，总复杂度是 $O(|S|^2)$ 的，下面介绍一种**后缀链接**的优化。 对于后缀树上结点 $s$，其等价类中最长串为 $S$，那么我们称 $S_2\ldots S_{|S|}$（即去除第一个字符）对应的点为 $s$ 的后缀链接，记为 $link$。 同时我们可以说明，若 $s$ 非叶子，那么其后缀链接的代表元就是 $S_2\ldots S_{|S|}$，这是因为 $s$ 至少有两个儿子，从而其代表元的一个后缀后面也至少有两种转移，所以它对应的后缀字典树上的点必然被继承在后缀树上。 那么，我们维护当前的最长隐后缀时，如果执行一次拆点后就要令隐后缀的长度减小 $1$，也就是删除隐后缀的首字符，那么我们只需要跳到其后缀链接处即可。 这里我们用一张图直观理解这一过程：图中实线为树边，虚线为一条后缀链接，蓝色箭头指向当前最长隐后缀，当我们加入字符 $d$ 时，首先拆点，然后将蓝箭头的位置跳到其后缀链接对应的同一条边（$\text{abc}$）的同一位置（$\text{b,c}$ 之间）上：  因此，只要我们能合理维护后缀链接和最长隐后缀位置，就能快速跳转到拆点后的下一个最长隐后缀位置，也就可以快速完成后缀树的构建。 而这个最长隐后缀位置只需要用二元组 $(p,l)$ 来描述，其中 $p$ 是这个后缀所在的边对应的父节点，而 $l$ 表示这个后缀在这条边的第几个字符后，那么只要 $p$ 不为根，我们跳转到下一最长隐后缀都是删掉 $p$ 祖先链上的第一个字符，也就是跳到其后缀链接处；而如果 $p$ 为根，那么我们要删除当前这条边的首字符，只需要将 $l$ 减少 $1$ 即可，注意我们并不需要标记最长隐后缀在哪条边上，因此这条边可以根据原串 $S$ 中对应的字符自动确定。 剩下的一步是我们需要维护所有非叶结点的后缀链接，对于拆出来的点（例如上图中非叶红点），我们只需要将其后缀链接设置为：**下一个拆出来的点（如果存在，如上图中 $\text{f}$ 这条链对应的 $\text{abc}$ 边之后拆出的一个点）或其父亲的后缀链接（如果拆不出点，我们根据上面的一些结论足以推出， $l=1$ 且这条边上的首字符就是当前插入的字符）**。 因此，优化完的 Ukkonen 算法描述如下： - 从前往后依次插入 $S$ 的每个字符； - 维护当前最长隐后缀 $(p,l)$，当前字符插入完成后使其自动增长（$l+1\rightarrow l$，若超过这条边长则调整 $p$），同时所有叶结点也自动增长（实现时只需将其长度设为 $+\infty$ 表示可以无限延申； - 插入字符时，尝试在当前边上拆点（如果根本不存在这条边即 $l=0$ 且不存在以插入字符为首字符的边，那么直接新建一个结点），如果成功拆点则跳转到后缀链接（如果 $p$ 不是根）或长度减小 $1$（如果 $p$ 是根），如果不成功（即上面所说的边上有一个相同字符导致无法拆点）则最长隐后缀维持，当前字符插入完成，无论哪种情况，都按照上面的规则维护新拆点的后缀链接。 - 为了最后使所有后缀都不是隐后缀，最后插入终止字符 $\Delta$。 可能更详细：EternalAlexander https://www.luogu.com.cn/blog/EternalAlexander/xuan-ku-hou-zhui-shu-mo-shu Ukkonen 算法的时间复杂度为 $O(|S|)$，这是因为我们每次以 $O(1)$ 的时间使最长隐后缀长度增加或减少 $1$，但其长度只增加了 $n$ 次。 --- 如果我们将后缀树重新“展开”成后缀字典树，那么之前建立的所有后缀链接是什么呢？其实就是所有后缀形成的 AC 自动机的失配指针，对比可以知道它们的定义是一致的，这也揭示了后缀数据结构和 AC 自动机之间的联系。 关于后缀树的更多性质，我们在介绍完另两种后缀数据结构后再统一分析。 --- ### 后缀数组的构建 取字符串 $S$ 的后缀构成的集合 $A$，将它们按照字典序进行排序，得到一个数组 $sa$，其中 $sa_i$ 表示第 $i$ 小的后缀编号，将此数组称为**后缀数组（Suffix Array，SA）**。 一般，我们还会同时求出 $sa$ 的逆排列 $rk$，其中 $rk_i$ 表示后缀 $i$ 的排名（这里后缀的编号指的是起始字符的位置），以及 $height_i$ 表示后缀 $sa_i$ 和 $sa_{i-1}$ 的最长公共前缀（LCP）（它的作用稍后说明）。 后缀数组只保留的后缀树的一部分信息，因为建立后缀树存在线性做法，因此**通常而言后缀树是比后缀数组更有力的工具**。 下面介绍后缀数组的构建算法，这里介绍两种比较简单的方法。 1. 字符串哈希法： 直接使用一个 sort 函数，将 cmp 定义为比较两后缀的字典序大小，而这一点我们可以利用字符串哈希在 $O(\log |S|)$ 的时间内完成。 总复杂度为 $O(|S|\log^2|S|)$。 2. 倍增法： 我们要求的是后缀的排名，不妨先做一部分：维护出所有 $S[i,\min(|S|,i+2^b-1)]$ 间的排名（也就是维护每个后缀的一个长度相等的前缀的字典序排名），然后从 $b$ 向 $b+1$ 扩展，直至 $b>\log |S|$，就完成了后缀的排序。 如何在线性复杂度内进行一次倍增呢？ 如果 $S[i,i+2^{b+1}-1]< S[j,j+2^{b+1}-1]$，则或者有 $S[i,i+2^b-1]<S[j,j+2^b-1]$，或者有 $S[i,i+2^b-1]=S[j,j+2^b-1]$ 并且 $S[i+2^b,i+2^{b+1}-1]<S[j+2^b,j+2^{b+1}-1]$。 所以我们只需要以 $S[i,i+2^b-1]$ 的相对大小为**第一关键字**，$S[i+2^b,i+2^{b+1}-1]$ 的相对大小为**第二关键字**进行基数排序，这样复杂度是 $O(|S|)$ 的，并且我们完成了一轮倍增。 总复杂度为 $O(|S|\log |S|)$。 现在我们得到了后缀数组 $sa$，而 $rk$ 本质上是一样的，下面来看如何求 $height$。 一种方法是仍然借助字符串哈希，我们可以简单地求出任何两个后缀的 LCP。 然而还存在一种线性做法，考虑 $height$ 数组的性质： **性质：$height_{rk_i}\ge height_{rk_{i-1}}-1$**。 证明：通俗地说，就是要证 $Suf(i)$ 和其后缀数组上前驱的 LCP 至少是 $Suf(i-1)$ 和其后缀数组上前驱的 LCP 减去 $1$。 这一点容易证明，设 $j=sa_{rk_i-1},\ k=sa_{rk_{i-1}-1}$，那么 $height_{rk_i}=LCP(Suf(i),Suf(j))$，而 $height_{rk_i-1}=LCP(Suf(i-1),Suf(k))$。 如果 $height_{rk_{i-1}}=0$，那么 $height_{rk_i}\ge -1$ 是显然的。 如果 $height_{rk_{i-1}}>0$，那么 $S_{i-1}=S_k$，又有 $Suf(k)<Suf(i-1)$，所以 $Suf(k+1)<Suf(i)$，并且 $LCP(Suf(i),Suf(k+1))$ 是从 $LCP(Suf(i-1),Suf(k))$ 中去掉第一个字符组成的，所以有 $LCP(Suf(i),Suf(k+1))\ge height_{rk_{i-1}}-1$。 如果 $k+1\ne j$，那么 $j$ 的字典序介于 $k+1,i$ 中间，所以 $k+1$ 和 $i$ 的公共前缀一定也是 $j$ 的前缀（因为要夹在当中），所以 $height_{rk_i}\ge LCP(Suf(i),Suf(k+1))\ge height_{rk_{i-1}}-1$。 上面的证明有些边界没有详细讨论，但仔细推敲可以发现不影响结论成立。 根据这一性质，我们依次确定 $height_{rk_1},\ldots,height_{rk_n}$，而求 $height_{rk_i}$ 时只需要以 $height_{rk_{i-1}}-1$ 为起点向后暴力比较即可，考虑 $height_i$ 的变化，总共只减了不到 $n$ 次，而每次加减都是 $O(1)$ 的，所以总复杂度为 $O(|S|)$。 后缀数组也存在直接的线性构建方法，例如 SA-IS，DC3 等，本文不涉及。 --- ### 后缀自动机的构建 建议先学习后缀树，否则可能看不懂。 **后缀自动机（Suffix Automaton，SAM）**是接受字符串 $S$ 所有子串的状态数最小的确定性自动机（似乎严格来说后缀自动机的终止状态是各后缀对应的状态，但这里不作具体区分，视作所有点都是终止状态）。 在这里限于作者能力，我并不能证明下面构造出的是最小的，本文中默认下面所描述的就是后缀自动机。 后缀自动机有一个起始状态 $s$，后缀自动机中的状态和后缀树上的结点比较类似： - 对于一个状态，$s$ 到它的所有路径构成了一个 $S$ 子串的 $\text{Endpos}$ 等价类。 注意这一句话描述的是一个很强的性质：它还隐含了 $S$ 的一个子串和后缀自动机上每条 $s$ 出发的路径是一一对应的，也即不存在两条 $s$ 出发的不同路径对应 $S$ 的同一子串。 根据之前后缀树的性质 $6$，我们直接得到关于 $\text{Endpos}$ 的结论： **结论：每个 $\text{Endpos}$ 等价类包含了一些长度形成公差为 $1$ 的等差数列的子串，其中短的串是长的串的后缀。** 设这个等价类为 $Sta$，将其中的最长子串称为 $L(Sta)$，则其中的所有子串是 $L(Sta)$ 的长度大于某一定值的所有后缀，令其中最长的长度为 $len(Sta)=|L(Sta)|$，最短的长度为 $mn(Sta)$。 类似于后缀树，我们定义**后缀链接**或 $link$： - 对于等价类 $Sta$，定义 $L(Sta)$ 的长度为 $mn(Sta)-1$ 的后缀对应的等价类为 $link(Sta)$。 也即是：$link(Sta)$ 表示的是 $L(Sta)$ 的最长的 $\text{Endpos}$ 集合与其不同的后缀对应的等价类。 不难证明 $len(link(Sta))=mn(Sta)-1$。 根据和后缀树中相同的规律，我们知道后缀链接将所有等价类连成一棵树。 但我们要的不是这个树，而是自动机结构，下面令 $f(p,c)$ 为状态 $p$ 经过字符 $c$ 转移到的状态。 讲了这么多前置的定义，下面该开始介绍后缀自动机的构建方法了，这里介绍的是最常见的 **Blumer 算法**： - 采用增量构造，每次向当前字符串 $S$ 末尾加入新字符 $c$，令 $S$ 对应的等价类为 $las$； - 由于 $S+c$ 一定产生了一个新等价类（$\{|S|+1\}$），所以新建一个结点，称为 $cur$； - 对于 $las$ 中的某个串 $T$，它是 $S$ 的后缀，并且 $T+c$ 不在 $S$ 中，然而现在末尾新增后 $T+c$ 就会出现在 $cur$ 状态，所以令 $f(las,c)=cur$； - 上面考虑了 $S$ 的长度为 $[mn(las),len(las)]$ 的后缀，下面考虑长度 $<mn(las)$ 的后缀，即跳到 $link(las)$ 处，如果当前 $link(las)$ 仍不存在字符 $c$ 的转移，那么同理令 $f(link(las),c)=cur$； - 如果 $las$ 一直跳到 $s$ 都能进行上述转移，那么 $c$ 是个之前从未出现过的字符，直接令 $link(las)=s$ 即可。 - 以此类推，直到 $las$ 的某个祖先 $p$ 存在字符 $c$ 的转移，令 $q=f(p,c)$： - 第一种情况，$q$ 代表的正好是 $p$ 后加上一个 $c$ 得到的所有串，那么我们直接令 $link(las)=q$ 即可，这一点类似 AC 自动机中的行为——$fail(x)=f(fail(fa_x),c_x)$。 - 否则，例如 $S=\text{ABC}$，$c=B$，那么此时的 $p$ 代表空串，而 $L(q)=\text{AB}$，并不是由 $p$ 后直接加 $\text{B}$ 形成的，这时它就不是 $las$ 的后缀了，所以 $las$ 的后缀链接要专门指向一个新点 $cp$，并且 $L(cp)=\text{B}$，可以将 $cp$ 看作 $q$ 的一份“复制”，除了缩短长度之外都和 $q$ 一致，由于它实际上是 $q$ 的后缀，所以要令 $link(q)=cp$，而 $link(cp)$ 是原来的 $q$：**本质上，这是将 $p\to q$ 这个转移中间拆成了两个不同类的转移 $p\to cp$ 和 $link(q)=cp$。** - 此时，类似于插入 $c$ 字符，对于 $p$ 的所有满足 $f(p',c)=q$ 的祖先 $p'$，由于 $cp$ 是一个夹在 $p'$ 和 $q$ 之间的串，所以要将 $f(p',c)$ 改成 $cp$。 与广义后缀树类似，可以建立多个串的广义后缀自动机，接受它们的子串的并。 广义后缀自动机的建立： - 先将所有串插入一棵 Trie，对 Trie 进行 DFS，类似 Blumer 算法插入每个点，以其父亲对应的点为 $las$ 插入即可。 Blumer 算法的复杂度证明：$O(|S|\times |\Sigma|)$，暂时懒得写。 可以用一个 map 维护 SAM 中的边，复杂度可优化至 $O(|S|\log |\Sigma|)$。 --- ### 联系与区别 后缀树是对一个字符串所有子串结构的一个简洁的概括。 后缀树的结构是自然的，因为所有子串的 $\text{Startpos}$ 等价类只有包含和不交，是树形关系，后缀树就是用于刻画这一树形关系的。 1. 后缀数组与后缀树的关系：后缀数组中的后缀排列顺序是按照后缀树从小字符到大字符的 DFS 序得到的，后缀树上的一个子树中的后缀对应了后缀数组的一个区间。 2. 后缀自动机与后缀树的关系：后缀自动机构造过程中的 $link$ 构成的树就是反串的后缀树结构，根据定义不难发现这一点。 3. 后缀自动机与后缀树的区别：后缀自动机是一个 DAG，而后缀树中不保存这一结构。 在本文中，我们将**后缀自动机中的 DAG 结构称为自动机结构，将其 $link$ 树称为树结构**。 接下来的结论揭示了**后缀自动机**和 **AC 自动机**的联系： - 后缀自动机可看作所有后缀构成的 AC 自动机的**压缩形式**，其中**自动机结构**对应 AC 自动机中的 **Trie 树**，而**树结构**对应 AC 自动机中的**失配树**，但我们一般建成的后缀自动机并没有添加除 Trie 边以外的边（在 BFS 过程中加的那些边）。 根据二者的定义不难说明这一点：AC 自动机的自动机结构接受所有子串，即所有后缀的前缀（如 Trie 树中接受所有其中串的前缀），而树结构对应的是当前点的最长后缀（如失配树的定义），唯一不同的是，**失配树**中的二度点被压缩，因此 Trie 树也被压成了 DAG 的样子，而不再是一棵树。 因此我们可以利用类似 AC 自动机的方法用后缀自动机解决多串匹配问题。 接下来的过程中，我们主要使用后缀自动机和 Blumer 算法解决问题，因为： - 后缀树可以通过建立反串 SAM 的 Blumer 算法顺便求出，Blumer 算法相对较好记忆； - 后缀数组的所有信息都包含于后缀树。 --- ### 常见维护技巧 在此之前，我们再次回顾自动机结构和树结构的性质： - 自动机结构：从起始点（称为 $1$）出发的所有路径和字符串 $S$ 的所有本质不同子串一一对应，$1$ 到一个定点的路径对应着一些互有后缀关系且长度连续的字符串集合。 - 树结构：以 $1$ 为根的有根树，互为祖先后代关系的点对 $\text{Endpos}$ 集合为包含关系，其他点对 $\text{Endpos}$ 集合为不交关系，父结点对应的最长字符串是子结点对应的最短字符串的最长真后缀，一个串的所有后缀是一条从某边端点或中间开始的祖先链。 --- **子串出现次数查询：求给定字符串 $S$ 的后缀自动机中每个结点代表的字符串出现了几次。** 答案即为每个结点的 $\text{Endpos}$ 集合大小，而由于其良好性质，一个结点的 $\text{Endpos}$ 集合是由其儿子的 $\text{Endpos}$ 集合直接求和（不交集合的并），再考虑其自身是否对应某个后缀。 因此首先将所有后缀对应点的答案加上 $1$，再进行树结构上的子树求和，即为答案。 时间复杂度为 $O(|S|)$。 --- > 例题 $6$： > > 求给定字符串 $S$ 的本质不同子串个数。 - 自动机结构上的解：即求自动机结构的从 $1$ 出发的路径数量，统计 DAG 上的路径数量容易使用拓扑排序解决。 - 树结构上的解：一个结点对应的不同子串的长度构成连续段，因此其数量就是该结点与其父结点 $len$ 的差，求和即可。 时间复杂度为 $O(|S|)$。 **扩展：求每个前缀的本质不同子串个数。** 解法：Blumer 算法每次插入一个字符后将答案加上当前最后一个点和其父亲的 $len$ 差。 --- >例题 $7$：[TJOI 2015] 弦论 > >求给定字符串 $S$ 的字典序第 $k$ 小子串，分别讨论位置不同的相同子串算作多个和一个的情况。 - 自动机结构上的解： 若位置不同的相同子串只算一次，即求 $1$ 出发的字典序第 $k$ 小路径，反向拓扑排序计算出每个点出发的路径数量，并从 $1$ 开始贪心即可。 若位置不同的相同子串算多次，那么我们给每个结点赋权为其对应字符串出现次数，将以其结尾的路径权值定义为其点权，再执行上面的算法即可。 - 树结构上的解： 由于字典序从前比较，所以要求反串的后缀自动机的树结构，即原串后缀树。 同样从根出发枚举儿子，贪心选取可以选的最小儿子，根据位置不同的相同子串算一个还是多个讨论子树大小的计算方法，和上面类似。 时间复杂度为 $O(|S|)$。 --- **子串定位：$m$ 次询问，每次给定 $S$ 的一个子串 $S[l\ldots r]$，求它在后缀自动机上属于哪个点的等价类。** 首先找到 $S[1\ldots r]$ 对应的点 $p$，这可以在执行 Blumer 算法时顺便记录。 由于 $S[l\ldots r]$ 是 $S[1\ldots r]$ 的一个后缀，所以它对应的等价类是 $p$ 在树结构上的祖先，而且是 $len$ 不小于 $r-l+1$ 的最近祖先，所以我们可以通过在树结构上倍增找到这个点。 时间复杂度为 $O((m+|S|)\log |S|)$。 --- **子串匹配：给定 $S$ 和 $T$，对每个 $r\in [1,|T|]$ 求最小的 $l$ 使得 $T[l\ldots r]$ 是 $S$ 的子串。** 令 $r$ 处的答案为 $f(r)$。 考虑递推计算 $pos(r)$ 和 $len(r)$，分别表示 $T[f(r)\ldots r]$ 在 $S$ 的后缀自动机上处于哪个等价类，以及 $r-f(r)+1$ 的值。 后缀自动机可以看成由所有后缀建成的 AC 自动机，所以我们按照 AC 自动机的方法进行匹配，并针对后缀自动机的特点稍作修改： - 计算 $pos(r)$ 和 $len(r)$ 时，首先令 $cur=pos(r-1)$ 和 $curlen=len(r-1)$； - 只要 $cur$ 不为 $1$ 且不存在 $T_r$ 这条出边，就跳转到 $lk(cur)$ 处（即失配指针处），并将 $curlen$ 设置为新的 $len(cur)$； - 如果 $cur$ 有了 $T_r$ 这条出边，就沿着这条边走一步，并 $curlen\leftarrow curlen+1$； - $pos(r)=cur$，$len(r)=curlen$。 注意，我们维护 $len(r)$ 的原因是：后缀自动机上一个点对应的子串长度不一，需要确切地知道是哪个。 时间复杂度为 $O(|S|+|T|)$。 **扩展：队列匹配，支持在 $T$ 的末尾加上字符或在开头删除字符，每次查询 $T$ 的后缀与 $S$ 的子串的最大匹配长度。** 解法：如果在开头删除字符，类似构建后缀树的 Ukkonen 算法过程，只需要将当前的 $curlen$ 减 $1$ 并检查是否已经到了树结构上父亲代表的等价类（如果是，就将 $cur$ 跳转到 $lk(cur)$）即可。 --- > 例题 $8$： > > 求 $m$ 个给定字符串 $S_1,\ldots,S_m$ 的最长公共子串。 不妨设 $S_1$ 是其中长度最短者。 对 $S_2,\ldots,S_m$ 分别建立后缀自动机，将 $S_1$ 分别与其进行子串匹配，求出 $len_x(r)$ 表示 $S_1$ 的前缀 $S_1[1\ldots r]$ 与 $S_x$ 的最大子串匹配。 则 $\max\limits_{r=1}^n \min\limits_{x=2}^m (len_x(r))$ 即为答案。 设 $L=\sum\limits_{i=1}^m |S_i|$，由于 $S_1$ 最短所以 $|S_1|\leq \dfrac{L}{m}$，因此复杂度为 $O(|S_1|\times m+L)=O(L)$。 --- **$\text{Endpos}$ 集合维护：求出 $S$ 的每个后缀自动机上每个点的 $\text{Endpos}$ 集合。** 在 Blumer 算法每次插入一个字符后当前终点的 $\text{Endpos}$ 集合是当前插入的字符。 此外，每个结点的 $\text{Endpos}$ 集合还要并上其儿子的 $\text{Endpos}$（事实上，儿子的 $\text{Endpos}$ 包括它自己本身的 $\text{Endpos}$ 都是不交的）。 可以采用线段树合并来维护，DFS 树结构时将父结点的线段树并上儿子的线段树，注意使用不销毁点写法的线段树合并。 然而维护出了 $\text{Endpos}$ 集合有什么用处呢？下面介绍一种最常见的应用。 **区间子“SAM”：** 对于给定字符串 $S$ 和一个子串 $S[l\ldots r]$，考虑如何得到有关 $S[l\ldots r]$ 的一些子串信息： 我们尝试通过 $S$ 的后缀自动机构建一个 $S[l\ldots r]$ 的后缀自动机，然而直接造出 SAM 是不可能的，我们只能保留其在匹配另一个字符串时的部分性质。 - 自动机结构： 对于每个原串后缀自动机中的转移 $u\to v$，设某个字符串在自动机上运行时走到 $u$ 时长度为 $len$，下面我们要解决的是：在只考虑 $S[l\ldots r]$ 的情况下，在当前长度为 $len$ 时 $u\to v$ 的这条转移是否可用。 为此，我们需要在原自动机上通过线段树合并求出每个点的 $\text{Endpos}$ 集合，然后考虑 $v$ 的 $\text{Endpos}$ 集合，我们实际上要判断对应点 $v$ 的长度为 $len+1$ 的串是否是 $S[l\ldots r]$ 的子串，那么我们找出 $v$ 的 $\text{Endpos}$ 集合中不超过 $r$ 的最大元素，设为 $w$，显然长度为 $len+1$ 的串是 $S[l\ldots r]$ 的子串就等价于它以 $w$ 结尾出现了一次，只需核验 $w-l+1\ge len+1$ 即可，如果满足则可以转移，否则不能转移。 - 树结构： $S[l\ldots r]$ 中一个子串的后缀仍然都在原自动机其祖先链上，因此在处理一般问题是树结构不需调整。 有了上面得到的一个子串 $S[l\ldots r]$ 的“SAM”（其实并不是 SAM），我们可以在 $O(|T|\log |S|)$ 的时间内直接完成另一个字符串 $T$ 在 $S[l\ldots r]$ 内的子串匹配。 与此同时，与 $\text{Endpos}$ 集合略有相关的内容此处另举一例。 **部分 SAM：** 给定字符串 $S$，对于每个 $r\in [1,|S|]$ 有一个最左限制 $f(r)\leq r$，利用 $S$ 的 SAM 得到有关所有 $S[f(r)\ldots r]$ 的子串并的信息。 处理方法和上面是类似的，令 $length(r)=r-f(r)+1$，对于每个点求其 $\text{Endpos}$ 集合中的最大值，即可知道这个点对应的实际对应存在的最长子串。 --- > 例题 $9$：[NOI 2018] 你的名字 > > 给定串 $S$，下有 $q$ 次询问，每次给定 $S$ 的子串 $S[l\ldots r]$ 和另一个字符串 $T$，求 $T$ 有多少本质不同子串不是 $S[l\ldots r]$ 的子串。 显然对于 $T$ 的每个前缀 $T[1\ldots v]$，有一个 $u$ 使得对所有 $w\ge u$，$T[w\ldots v]$ 都是 $S[l\ldots r]$ 子串，而对所有 $w<u$，$T[w\ldots v]$ 都不是 $S[l\ldots r]$ 的子串，将这个 $u$ 称为 $lb(v)$。 如何求出 $lb(v)$？不难发现这只是 $T$ 的每个前缀和 $S[l\dots r]$ 的子串匹配，利用上面说的“区间子 SAM”的技巧即可在 $O(|T|\log |S|)$ 的时间内求出。 最后要求 $T$ 的不是 $S[l\ldots r]$ 子串的子串数，思考时不妨转化成是 $S[l\ldots r]$ 子串的子串数，而这其实就是 $T$ 的一个部分 SAM 的本质不同子串数量，使用上面的技巧容易求出。 实现时，并不需要维护 $T$ 的后缀自动机上所有点的整个 $\text{Endpos}$ 集合，根据 $lb(v)$ 数组的一些性质，只需要保留每个点 $\text{Endpos}$ 集合中的最大值即可。 时间复杂度为 $O((|S|+\sum |T|)\log |S|)$。 --- **扫描线+LCT 维护区间子串信息：** 此处以求**多次询问区间本质不同子串**为例，介绍一类使用扫描线+LCT 维护区间子串信息的方法。 设给定的区间为 $S[l\ldots r]$，对于 $S$ 的每一个子串 $T$，求出其不超过 $r$ 的最后一次出现的右端点，设为 $rb(T)$，如果 $l\leq rb(T)-|T|+1$，那么它就对 $S[l\ldots r]$ 的本质不同子串有贡献。 考虑询问离线后按照 $r$ 从左到右扫描，用 Blumer 算法每次插入一个字符进后缀自动机，设当前加入了 $S[1\ldots r-1]$，现在要加入 $S_r$，加入后设 $S[1\ldots r]$ 对应结点为 $p$，我们需要将 $p$ 的所有祖先对应的 $rb(T)$ 修改为 $r$。 对于某一个点，设其 $rb(T)$ 为 $u$，字符串长度区间为 $[tl,tr]$，用线段树维护答案，那么我们就将 $[u-tr+1,u-tl+1]$ 这个区间都加上 $1$，随后访问 $[l,n]$ 的区间和就是 $S[l\ldots r]$ 的本质不同子串数量。 因此一种暴力的思路是：访问 $p$ 的每个祖先，分别进行一次区间减，最后再统一将区间加 $1$。 然而此做法复杂度错误，要得到一种复杂度正确的算法，我们需要借助 LCT 的分析方法： - 用一个 LCT 维护当前 SAM 的树结构，使得**每条实链上的点对应的 $rb$ 都相同**，这样，修改时我们只需对 $p$ 进行一次 Access，这样就可以处理 $p$ 到根的所有实链，先除掉它们的所有贡献，再建立 $p$ 到根的整条实链，其 $rb$ 值为 $r$，进行一次区间加即可。 由于所有操作都是 LCT 上的自然操作，根据 LCT 的理论可以直接说明复杂度是正确的。 时间复杂度为 $O(n\log^2 n+m\log n)$，其中 $m$ 是询问数量。 --- > 例题 $10$：[集训队作业 2018] 后缀树节点数 > > 给定字符串 $S$，$m$ 次询问，每次给定区间 $[l,r]$，求 $S[l\ldots r]$ 的后缀树结点数。 赞歌。 感觉我出的力脑和这题解法可能有一点关系。 --- ### 其他技巧 这里主要介绍一些后缀自动机的外沿内容和后缀数组的一些技巧。 --- **广义 SAM 出现子串查询：对于 $n$ 个串的广义后缀自动机，求出每个点对应的字符串是哪些原串的子串。** 方法和线段树合并维护 $\text{Endpos}$ 集合基本一致，将每个后缀对应的点附上对应串的标记，然后在树结构上 DFS 进行线段树合并即可得到每个串的出现位置。 --- > 例题 $11$：[CF 666 E] Forensic Examination > > 给定字符串 $S$ 和 $m$ 个字符串 $T_1,\ldots,T_m$，有 $q$ 个询问，每次询问 $S[pl\ldots pr]$ 在 $T_l,\ldots,T_r$ 中哪个字符串里出现次数最多，如果最大值不唯一则取最靠前的。 首先建出 $T_1,\ldots,T_m$ 的广义 SAM，然后询问就分成两步： - 求出 $S[pl\ldots pr]$ 在 SAM 上的位置 $p$，这可以通过之前介绍的子串定位完成； - 求出点 $p$ 在 $[l,r]$ 中哪个 $T_i$ 出现次数最多，这可以用线段树合并维护每个点在每个串的出现次数，然后查询区间最大值得到。 令 $L=\sum\limits_{i=1}^m |T_i|$，时间复杂度为 $O((L+m)\log L+|S|)$。 --- **两个后缀的最长公共前缀（LCP）：** 建立反串的后缀自动机（或原串后缀树），根据树结构的意义可知两个后缀的最长公共前缀对应的点是这两个后缀对应的点的 LCA。 而此问题在后缀数组上也有一种相应的做法。 考虑后缀数组中 $height$ 的实际含义，如果放到后缀树上就是 DFS 序相邻的两个关键点的 LCA 深度，假设我们要求排名为 $l,r$ 的两个后缀的 LCP，那么按照 $l\to l+1\to \ldots\to r-1\to r$ 这个顺序来走，走到的最浅的点就是答案，那么这个答案的深度就是 $\min\limits_{i=l+1}^{r} height(i)$。 从这个角度理解，后缀树和后缀数组的关系有点类似于笛卡尔树和数列的关系（但并不是）。 所以，许多类后缀树上数据结构合并的问题都可以通过后缀数组 $height$ 数组的笛卡尔树合并来实现。 --- > 例题 $12$：[NOI 2015] 品酒大会 > > 给定字符串 $S$，每个后缀有整数权值 $a_i$，对于每个 $i\in [0,|S|-1]$ 输出有多少对后缀的 LCP 长度不小于 $i$，并输出这些后缀对中权值之积的最大值。 最经典的一道题目。 将后缀数组中 $height$ 从小到大排序扫描，初始每个后缀记为一个连续段，遇到一个 $height$ 相当于合并了其两边的连续段，并且两边的贡献对应的 LCP 值就是当前的 $height$，而权值之积的最大值只需要用 ST 表分别维护区间最大值和最小值即可（最大的乘积只可能是最大乘最大或最小乘最小）。 可以使用类似链表的结构或线段树维护连续段，时间复杂度为 $O(|S|\log |S|)$。 --- **后缀平衡树：** 要求维护一个初始为空的字符串，支持 $n$ 次操作，操作为前端的插入字符以及查询一个后缀的当前排名。 对于前端插入并维护后缀结构，我们通常有两种维护思路： 1. 建立反串的后缀自动机，在 Blumer 算法的实现中采用 LCT 维护树结构，即可支持动态的加边和一些查询。 不过本题要查询后缀排名，对于 SAM 来说不太友好。 2. 采用后缀平衡树。 后缀平衡树是将后缀数组的信息放到一棵**重量平衡树**上维护，支持插入一个新的后缀（即前端增加一个字符）。 首先，我们需要维护当前所有后缀的“绝对排名”：用一个**实数** $f_i$ 表示后缀 $i$ 的排名，$f_i<f_j$ 表示后缀 $i$ 比后缀 $j$ 小。 那么如何维护这个绝对排名呢？考虑到我们是在平衡树上，让平衡树的中序遍历为 $f_i$ 的上升序，那么在插入时令一个点的 $f$ 值取其前驱后继的平均，而为了防止掉精度，所以我们采用了重量平衡树，在重构时可以直接按照完美二叉树的分治结构赋予比较平均的新 $f$ 值。 随后，插入时我们按照和平衡树中插入相同的方法，从根开始向下走，每次比较插入后缀和当前点后缀的大小，具体地： - 设插入字符为 $c$，当前点后缀的首字符为 $d$，如果 $c\ne d$ 则已经比较完成； - 如果 $c=d$，那么去掉首字符后比较的是两个既有后缀的大小，直接根据 $f$ 值即可 $O(1)$ 比较。 插入的过程中可以顺便求出前驱后继，也就可以求出这个点的 $f$ 了，注意树的重构。 由于比较两个现有后缀大小是 $O(1)$ 的，所以该算法的复杂度为 $O(n\log n)$。 而如果朴素地采用哈希实现后缀数组，也可以利用一些数据结构完成前端插入，但复杂度通常无可避免地达到 $O(n\log^2 n)$ 以上。 --- **你已经学会基本的几种字符串数据结构动态维护技巧了，下面来做几道例题试看看吧！** > 例题 $13-1$： > > （题目来源：我的口胡）String Master L > > 维护一个初始为空的字符串 $S$，支持 $n$ 次操作，操作为： > > - 末尾插入； > - 给定字符串 $T$ 查询其在当前 $S$ 中的出现次数。 > > $n,\sum |T|$ 同阶。 **解法一：我会 AC 自动机。** 离线后建出所有模式串的 ACAM，然后用最终的 $S$ 在上面走，一边走一边记录 ACAM 上每个点与 $S$ 的哪些后缀有匹配，然后对 AC 自动机进行线段树合并，最终统计答案。 **解法二：我会后缀自动机。** 建出最终 $S$ 的后缀自动机，并且线段树合并维护 $\text{Endpos}$ 集合，然后对于每个 $T$ 进行子串匹配，询问对应点的 $\text{Endpos}$ 集合中一个前缀的和即为答案。 **解法三：我会动态后缀结构。** 采用 SAM+LCT 或者后缀平衡树的技术维护带插入的字符串 $S$，然后可以直接查询。 这些做法中，大部分时间复杂度都是单 $\log$，但是后缀平衡树由于无法直接支持查询后缀与另一个字符串的大小，所以复杂度在 $\sum |T|$ 上可达 $\log^2$。 --- > 例题 $13-2$： > > （题目来源：我的口胡）String Master XL > > 维护一个初始为空的字符串 $S$，支持 $n$ 次操作，操作为： > > - 末尾插入； > - 末尾删除； > - 给定字符串 $T$ 查询其在当前 $S$ 中的出现次数。 > > $n,\sum |T|$ 同阶。 **解法一：我会 AC 自动机。** 类似上题，不过在维护时间时带上一点技巧（将删除也看做时间轴上的一点，用栈维护 $S$ 在 ACAM 上的行动轨迹）。 **解法二：我会后缀自动机。** 后缀自动机的构造复杂度证明是均摊的，反复插入删除可以让它爆炸。 噔噔咚（未知有无可行办法）。 **解法三：我会后缀平衡树。** 如果用后缀平衡树，和上题基本没什么区别。 --- > 例题 $13-3$： > > （题目来源：我的口胡）String Master XXL > > 维护一个初始为空的字符串 $S$，支持 $n$ 次操作，操作为： > > - 末尾插入； > - 首端插入； > - 给定字符串 $T$ 查询其在当前 $S$ 中的出现次数。 > > $n,\sum |T|$ 同阶。 这部分和字符串倒关系不大，主要是一个数据结构上的技巧。 将首端插入的字符串和末尾插入的字符串看成两个独立的串 $S_1,S_2$，分别用 $13-1$ 的方法维护。 对于询问，分成三部分： - $T$ 在 $S_1$ 中的出现：同 $13-1$； - $T$ 在 $S_2$ 中的出现：同 $13-1$； - $T$ 在 $S_1,S_2$ 交界处的出现：考虑到这部分涉及的字符总数不到 $2|T|$，暴力拿出来做个 KMP 即可。 --- > 例题 $13-4$： > > （题目来源：我的口胡）String Master XXXL > > 维护一个初始为空的字符串 $S$，支持 $n$ 次操作，操作为： > > - 末尾插入； > - 末尾删除； > - 首端插入； > - 首端删除； > - 给定字符串 $T$ 查询其在当前 $S$ 中的出现次数。 > > **强制在线。** > > $n,\sum |T|$ 同阶。 关于这题：去年寒假的时候出完这题觉得自己很 nb，本来想出到公开赛里的，然后问了下发现很久以前有个差不多的题，被爆了。 由于强制在线，所以之前的 AC 自动机解法是比较难了。 **解一：正统的动态后缀数据结构：** 将 $13-2$ 和 $13-3$ 进行结合，分成前后两个部分维护。 由于这时候有删除了，所以其实前后分别是个栈，采用两个动态后缀结构分别维护，对于跨过分界点的贡献用 KMP 暴力计算。 看上去很好，但这个做法有漏洞：如果其中一个栈被删完了，但还要继续从这端删除，怎么办呢？ 答案是：当一个栈被清空时，就重构整个结构，将另一个栈中的元素平分后再作为新的两个栈。 复杂度简单理解一下：每个元素除了第一次插入外每次被重构到，一定有等量的元素被删除，所以每个字符被重构的次数和应当是和操作数线性的。 如果采用后缀平衡树，复杂度可能达到 $2$ 个 $\log$，而采用 SAM+LCT 应该能做到 $1$ 个 $\log$（这里不确定行不行）。 不过实情是我自己也没写过这题。 **解二：哈希文艺复兴：** 我们就完全用比较无脑暴力的哈希和 KMP 来解决问题！ 然后想想什么东西比较贴合暴力算法的需要，那就是根号分治： - 如果 $|T|\leq B$，那么我们可以用一个 $\text{set}$ 维护 $S$ 的所有长度不超过 $B$ 的子串哈希值，然后直接查询 $T$ 的哈希值出现了几次。 当然，这部分的 $\text{set}$ 再用另一个哈希表代替也是可以的。 总复杂度为 $O(nB\log n)$ 或 $O(nB)$。 - 如果 $|T|>B$，那么这样的 $T$ 就不超过 $\dfrac{n}{B}$ 个，所以暴力和 $S$ 做一次 KMP。 总复杂度为 $O(\dfrac{n^2}{B})$。 然后平摊一下二者复杂度，可以得到 $O(n\sqrt {n\log n})$ 或 $O(n\sqrt n)$ 的优秀做法（取决于是否使用 $\text{set}$）。 --- ## 5. 回文串结构 这里讨论的是一个回文串或一个串的所有回文子串的结构。 回文串有许多优美的性质，下面以一个经典算法为例： --- > 例题 $14$： > > 给定字符串 $S$，求出以所有字符（包括相邻字符之间位置）为回文中心的最长回文子串。 这题的经典解法是 Manacher 算法。 首先，我们在 $S$ 的开头，结尾，以及相邻两字符之间分别加上三种不同分隔符，这样“相邻字符之间位置”就被显式表达出来，同时避免很多边界讨论。 用 $ans_i$ 表示以 $i$ 为回文中心的最长回文半径（即长度一半上取整），从左到右扫描，记当前 $i+ans_i$ 最大的位置为 $mid$。 当前计算 $ans_x$： - 若 $ans_x\ge mid+ans_{mid}$，那么将 $ans_x$ 初始化为 $0$，否则将其初始化为 $ans_{2\times mid-x}$； - 此后尝试扩展 $ans_x$：即若 $S_{x+ans_x}=S_{x-ans_x}$ 则令 $ans_x\leftarrow ans_x+1$。 考虑上述过程的意义：$2\times mid-x$ 是 $x$ 在回文串 $S[mid-ans_{mid}+1\ldots mid+ans_{mid}-1]$ 中的对称位置，在这个回文串部分中两个点为中心的最长回文子串应当是相等的。 也就是说，如果 $x+ans_x<mid+ans_{mid}$，那么 $ans_x$ 必定无法在第二步中进行扩展（在回文串内部已经走不下去了），所以必然不会在第二步中被扩展。 类似地，在第二步中被扩展一次后由于 $x+ans_x>mid+ans_{mid}$，所以 $x$ 必然会成为新的 $mid$，也就是说对于每个 $x$，除了最后一次失败的比较外都会使得 $mid+ans_{mid}$ 的值增加 $1$，所以复杂度就是 $O(|S|)$ 了。 --- 这里运用到了回文串的对称性。 类似地，我们可以得到一个回文子串的基本性质： **性质：长度为 $n$ 的字符串的本质不同非空回文子串数量不超过 $n$。** 证明： 考虑以 $x$ **结尾**的回文子串 $S[x-len+1\ldots x]$，称它是**独特的**，当且仅当不存在 $y<x$ 使得 $S[y-len+1\ldots y]=S[x-len+1\ldots x]$。 如果以 $x$ 结尾有两个不等长回文子串 $S[x-a+1,\ldots x]$ 和 $S[x-b+1\ldots x]$，不妨设 $a<b$，根据回文串的对称性有 $S[x-a+1\ldots x-a+b]=S[x-b+1\ldots x]$，所以 $S[x-b+1\ldots x]$ 不是以 $x$ 结尾的独特回文子串。 因此以每个 $x$ 结尾的独特回文子串只有最多一个（最长的那个），而每个本质不同回文子串都会在其中被算一次，所以不超过 $n$ 个。 下面介绍的回文树描述了一个串的所有本质不同回文子串之间的关系。 ### 回文树 **定义：将一个回文串从回文中心开始的后缀称为其半串。** 将字符串 $S$ 的每个本质不同非空回文子串作为一个点，定义一个点的父亲为它对应的串删去两端的字符后得到的串对应的点。 这样，长度为 $1$ 或 $2$ 的串找不到父亲，我们定义两个“虚根”，分别称为偶根和奇根，作为长度为 $2$ 和 $1$ 的点的父亲，将它们对应的长度记作 $0$ 和 $-1$。 可以看出，回文树可以看成是所有本质不同回文子串**的半串**构成的 Trie，但对奇数和偶数分开了（事实上可以看作在奇数或偶数部分的开头多加了一位标识符，把两个根统一，但我们下面不采用这个意义）。 有了 Trie 我们自然思考构建 AC 自动机，我们可以直接建出 AC 自动机，但因为有了两个根，我们作如下初始化，先变成一棵树： 将奇根的所有儿子初始化为偶根，偶根的失配指针指向奇根，同时我们将奇根指向偶根的边也当成空边处理（即遇到新字符时就将这条边指向一个新结点）。 如此建出的 AC 自动机上，每个点的失配指针**的半串是它对应的半串的在树上的最长真后缀**，将半串转化为回文串，就会得到： **性质：回文串的 Border 是回文串，且一个点对应的回文子串的最长回文 Border 是它在回文树上的失配指针对应的回文串。** 回文树因为有了 AC 自动机的结构，所以也称为**回文自动机（PAM）**。 那么，我们如何快速构建回文自动机呢？ ### 回文自动机的构建 这里介绍一种常用的在线构造失配指针的构建方法。 记当前字符串的最长回文后缀对应的点为 $las$，当前字符串长度为 $A$，在末尾新增一个字符 $S_{A+1}=c$ 时： - 通过跳 $las$ 的失配指针，找到 $las$ 对应的串的一个最长 Border $S[A-len+1\ldots A]$，使得 $S_{A-len}=c$，这样我们就找到了以 $S_{A+1}=c$ 结尾的最长回文串 $S[A-len\ldots A+1]$（最长性可以用反证法证明）； - 如果这个串已经出现过，那这一轮插入已经结束了（因为这意味着 $S_{A+1}$ 结尾的所有回文子串都已经在前面出现过）； - 否则，我们加入这个点，然后计算它的失配指针，利用和第一步相似的方法，我们从当前点的父亲开始不断跳失配指针，直到再找到一个 $S_{A-len}=c$ 的点，其出边 $c$ 对应的点就是当前加入点的失配指针。 时间复杂度为 $O(|S|)$，复杂度证明赞歌。 --- ### 常见维护技巧 由于 PAM 和 SAM 本质上都可看作 ACAM，所以这里列举的一些应用也是相似的。 **回文子串出现次数：统计 $S$ 的每个本质不同回文子串的出现次数。** 类似后缀自动机地，我们只需要在每个前缀的最长回文后缀处将答案增加 $1$，再在失配树上做个子树求和即可。 **$\text{Endpos}$ 集合维护：统计每个本质不同回文子串所有出现的终止位置。** 类似后缀自动机地，在失配树上线段树合并。 **回文子串匹配：给定 $S,T$，求 $T$ 的每个前缀的最长的是 $S$ 子串的回文后缀。** 类似后缀自动机地，在当前点能走对应出边时就走一步，否则就跳失配指针。 --- > 例题 $15$： > > 给定 $m$ 个字符串 $S_1,\ldots,S_m$，求最长公共回文子串。 不妨设 $S_1$ 为其中最短者。 分别将 $S_1$ 与 $S_2,\ldots,S_m$ 进行回文子串匹配，最后求 $S_1$ 每个前缀对所有其他串匹配长度的最小值的最大值。 匹配复杂度为 $O(|S|+|T|)$，由于 $|S_1|\leq \dfrac{\sum |S_i|}{m}$，所以总复杂度 $O(\sum |S_i|)$。 --- ## 6. Lyndon 理论 此部分将不会在 NOI2022 前更新。