浅谈串串题里的自动机

· · 个人记录

浅谈串串题里的自动机

众所周知，字符串问题里会涉及到一车自动机模型的算法，这里写点东西简单总结一下。

一些内容概要和基本概念

本文会涉及到三个自动机：\sf AC 自动机（\sf ACAM），后缀自动机（\sf SAM）和回文自动机（又称回文树，\sf PAM）。当然这些知识点稍微有些难度，所以这里先用一个比较简单的自动机——\sf Trie 树，作为引入和热身吧。

首先，OI 中讨论的自动机一般为确定有限状态自动机（\sf DFA），它能被一张 \sf DAG 表示，且由五个部分组成：

对于一个 \sf DFA，我们可以把拿一个字符串在上面转移的过程，看成在它对应的 \sf DAG 上走的过程，而最终到达的结点会返回一个结果。即，\sf DFA 可以识别一个字符串。

我们来看看 \sf Trie 树对应的这五个部分。

对于 \sf Trie 树，我们可以拿一个字符串在上面沿着 \delta 走结点，如果最终走到的结点有结束标记，则说明这个字符串曾经被插入过 \sf Trie 树内。（当然插入的过程也是类似的，不再赘述）

相信大家已经理解 \sf DFA 是什么了，那接下来就进入正题吧。（注意：因为如果把这仨自动机全都详细介绍一遍，那本文就有点太长了，所以建立自动机部分制作简单介绍）

AC 自动机

具体来讲，我们在 $\sf Trie$ 树上匹配时，如果出现失配，就只能回到根节点再来一遍，这是非常不划算的，不仅如此，我们匹配上时，还要考虑这个状态的后缀是不是也在 $\sf Trie$ 树里。等等，后缀？我们发现，如果能找到一个状态，满足是当前状态的最长后缀，那不就能解决以上两个问题了吗！ 这里就要引出加速自动机匹配的最重要的一个概念了，后缀链接，一般称作 $\sf fail$。就像刚刚介绍的，$\sf fail$ 指针指向的是，**在自动机里当前状态的最长后缀**，当我们失配时就可以走到 $\sf fail$ 指针对应的位置继续匹配，而当我们匹配上时，就可以沿着 $\sf fail$ 指针继续跳，直到跳到根，就能找到所有匹配上的后缀了。 在 $\sf AC$ 自动机上，建立 $\sf fail$ 指针可以基于它在 $\sf DFA$ 上的前置状态（也就是在 $\sf DAG$ 上指向它的那个状态）的 $\sf fail$ 来得到，具体实现可以用 $\rm bfs$。 接下来，就用在这仨里面相对简单一点的 $\sf AC$ 自动机来介绍一下自动机上能干啥。 #### 字符串匹配 > [P5357 【模板】AC 自动机（二次加强版）](https://www.luogu.com.cn/problem/P5357) > > 给出一个文本串 $S$ 和 $n$ 个模式串 $T_{1\sim n}$，请你求出每个模式串 $T_i$ 在 $S$ 中出现的次数。($1\le n,\sum T_i,|S|\le 2\times 10^5$) 考虑我们匹配的过程，就是用文本串在 $\sf AC$ 自动机上走一遍，这部分的时间复杂度是 $\mathcal{O}(|S|)$ 的。而找到终止结点时，我们需要跳 $\sf fail$ 指针来找到所有出现的后缀，这部分的时间复杂度最坏可以到 $\mathcal{O}(n)$，而两者是乘法的关系，所以朴素的匹配是 $\mathcal{O}(n|S|)$ 的复杂度，显然不够优秀。 观察我们跳 $\sf fail$ 指针的过程，看起来很像给一条链上所有的结点加 $1$，而直觉告诉我们，这个过程是很可以优化的。观察 $\sf fail$ 指针构成的结构，因为除了 $s$ 状态，所有状态都有对应的 $\sf fail$ 出边，即如果总状态有 $p$ 个，则我们有 $p-1$ 条边。而注意到 $\sf fail$ 指针形成的结构是连通的（感性理解吧，咱这儿没有证明），所以我们就可以把 $\sf fail$ 指针单独拉出来形成一棵树。一般叫做 $\sf fail$ 树。 则我们跳 $\sf fail$ 的过程就可以变为在 $\sf fail$ 树上朝根走的过程。这样的话，我们就可以用我们学过的树相关的算法对这个过程加以优化了。用树上差分，可以做到 $\mathcal{O}(|S|+\sum T_i)$ 的复杂度。 代码：[$\tt code$](https://www.luogu.com.cn/paste/5u3fsnmj)。 #### fail 树 刚刚提到的 $\sf fail$ 树在不同的自动机可能有不同的叫法，但总的来说都是把 $\sf fail$ 指针形成的结构变成树这么一个我们熟知的结构，从而能用我们熟知的算法加以解决，这个功能是十分强大的。不过要注意区分 $\sf DFA$ 本身和 $\sf fail$ 树。 > [P2414 [NOI2011] 阿狸的打字机](https://www.luogu.com.cn/problem/P2414) > > 给出 $n$ 个字符串和 $m$ 组询问，每组询问需要回答第 $x$ 个字符串在第 $y$ 个中出现了多少次。($1\le n,m\le 10^5$) 原题的这 $n$ 个字符串就是以 $\sf Trie$ 树的形式给出的，~~做法甩脸上了~~。建出来 $\sf AC$ 自动机后，考虑 $\sf fail$ 指针的意义，即最长的后缀，而注意到 $\sf AC$ 自动机上的状态集合是前缀，前缀的后缀......是子串！这刚好和我们想要的东西不谋而合，所以我们要考虑的状态是 $\sf DAG$ 上 $y$ 对应的结束状态到 $s$ 路径上的所有状态。需要考虑的状态中，每个对应的贡献就是它在 $\sf fail$ 树上到根节点的路径上，出现的状态中，在 $x$ 状态子树内的状态个数。 所以我们相当于询问，$\sf DAG$ 上的一条链上所有结点，在 $\sf fail$ 树上的到根节点的路径上在 $x$ 状态子树内出现的次数和。由于子树在 $\rm dfn$ 序上对应的是一段区间，所以这个可以用主席树实现，每个状态用它在 $\sf DAG$ 上的前置结点作为上一个根即可，维护每个 $\rm dfn$ 序对应的结点出现了多少次。时间复杂度 $\mathcal{O}(m\log n)$。 代码：[$\tt code$](https://www.luogu.com.cn/paste/6pefics5)。 #### 动态规划 我们发现，$\sf DFA$ 的结构是一个 $\sf DAG$，这不跑 $\rm dp$ 亏了。 > [P5319 [BJOI2019]奥术神杖](https://www.luogu.com.cn/problem/P5319) > > 给出一个长为 $n$ 的字符串 $S$，其中一些位置可以选择。再给出 $m$ 个串和对应的价值 $(s_i,v_i)$，如果在选择 $S$ 中空缺的字符后，可重集 $S=\{s_i\}$ 内的字符串在 $S$ 中出现（出现多次统计多次），则价值为： > $$\sqrt[|S|]{\prod_{i=1}^{|S|}v_i}$$ > 求最大价值，输出一种对应的方案。($1\le n,m,\sum |s_i|\le 1501,1\le v_i\le 10^9$) 观察到这个式子很恶心，没法统计（你甚至没法计算），所以要做点变化： $$\begin{aligned}&\max \sqrt[|S|]{\prod_{i=1}^{|S|}v_i}\\=&\max \ln\sqrt[|S|]{\prod_{i=1}^{|S|}v_i}\\=&\max \dfrac{1}{|S|}\sum_{i=1}^{|S|}\ln v_i\end{aligned}$$ 所以我们现在的目标就从最大化原来那个恶心的根式，变成最大化后面那个和式。注意到这是 $0/1$ 分数规划的形式，考虑二分一个答案 $x$，则二分的条件： $$\begin{aligned}\dfrac{1}{|S|}\sum_{i=1}^{|S|}\ln v_i&>x\\\sum_{i=1}^{|S|}\ln v_i&>x|S|\\\sum_{i=1}^{|S|}(\ln v_i-x)&>0\end{aligned}$$ 所以现在我们的目标就是，对于 $x$，最大化左边那个式子，然后比较它和 $0$ 的关系，从而找到二分应该如何调整左右边界。 而我们想求出这个值，只需要给 $\sf AC$ 自动机上每个状态的权值设置为它在 $\sf fail$ 树上到根结点的权值和即可，状态初始权值仅有结束状态有，为 $\ln v_i$，并记录每个状态到根结点的状态数 $\rm cnt$，每次给每个结点减去 $x\rm cnt$ 即可。考虑 $\rm dp$，设 $f_{i,j}$ 表示前 $i$ 个字符，匹配到第 $j$ 个状态，能得到的最大权值，转移的时候直接按照刚刚求好的权值加一加即可。注意，这里要按照拓扑序来转移，而由于 $\sf AC$ 自动机构建的特殊性，加入结点的顺序就是拓扑序，直接做就好了。记得再维护一下路径以便输出答案。时间复杂度 $\mathcal{O}(n\sum |s_i|\log \log v_i)$。 代码：[$\tt code$](https://www.luogu.com.cn/paste/y6n1eoqv)。 当然 $\rm dp$ 也有很多种，不止可以做这道题最大化类型的 $\rm dp$。状压，数位等等都可以做，非常灵活。 #### 图的结构 $\sf DAG$ 和 $\sf fail$ 树毕竟也是图的一种，有没有可能，用它们的结构干点什么呢。（提一嘴，这种结构叫 $\sf Trie$ 图，我们刚刚匹配就一直在用这个） > [P2444 [POI2000]病毒](https://www.luogu.com.cn/problem/P2444) > > 给出 $n$ 个 $\tt 0,1$ 串 $s_i$，求是否存在一个无限长的串不包含里面的任意串。($1\le n\le 2\times10^3,1\le \sum |s_i|\le 3\times 10^4$) 考虑我们匹配的过程，是找到结束结点的过程，而本题要求我们尽量在匹配的时候不找到结束结点，并问能否一直走下去。建出来 $\sf AC$ 自动机对应的 $\sf Trie$ 图后，我们就在这张图上面走，如果能走进一个环，且环上所有结点没有结束结点，也不会匹配到有结束结点的状态，那我们就可以在这张环上一直走，从而找到一个无限长的串。对于结束结点的维护，可以用刚刚奥术神杖那道题的思路，而找环就是一遍 $\rm dfs$ 的事。时间复杂度 $\mathcal{O}(\sum |s_i|)$。 代码：[$\tt code$](https://www.luogu.com.cn/paste/q8ah0kfe)。 $\sf AC$ 自动机的介绍就暂时到此为止了，因为笔者想不起来什么其他的用处了。（如果您有想法欢迎在讨论区提出！）接下来，让我们移步，来看看一个强大的自动机，$\sf SAM$。 ### 后缀自动机 后缀自动机（通常简称为 $\sf SAM$，$\sf Suffix\ Automaton$），是一种能用于 **大部分字符串问题** 的 $\sf DFA$，它以高度压缩的形式存储了一个字符串的所有子串信息，也就是说，它的状态集合是一个字符串的所有子串。而结束状态，就像它的名字一样，是一个字符串的所有后缀。不仅如此，$\sf SAM$ 是满足以上性质的自动机中，状态数和转移数最少的。 $\sf SAM$ 的压缩，是基于 $\sf endpos$ 集合（在原串中出现的结束结点集合）的，它把 $\sf endpos$ 集合相同的一类子串压缩成一个状态，且由于 $\sf endpos$ 集合的优秀性质，我们能通过这个状态得知许多信息。（以下 $\sf endpos$ 简称 $\sf edp$）建立 $\sf SAM$ 的过程不再赘述，具体可以看 OI wiki 或者 [$\tt cmd$ 的博客](https://www.luogu.com.cn/blog/command-block/hou-zhui-zi-dong-ji-xue-xi-bi-ji)，接下来说一些 $\sf SAM$ 的性质： 1. $\sf SAM$ 是由一个 $\sf DFA$ 和上面的后缀链接 $\sf fail$ 组成的，而 $\sf fail$ 组成的 $\sf fail$ 树又被称为 $\sf parent$ 树，$\sf fail$ 指针连向的状态是该状态内最长串最长的不在该状态内的后缀，所在的状态。 2. $\sf SAM$ 上每个结点表示的子串互为后缀关系，且长度连续，在 `a[a[p].f].len + 1` 到 `a[p].len` 之间，其中 `f` 是后缀链接，`len` 是该状态内最长串的长度。 3. $\sf SAM$ 每个结点 `p` 表示的子串个数是 `a[p].len - a[a[p].f].len`。 4. $\sf edp$ 集合要么不交，要么相互包含，且 $\sf parent$ 树上的非叶子结点的 $\sf edp$ 由子节点并得到。 5. 反串的 $\sf parent$ 树是原串的后缀树。 6. 随机字符串的 $\sf parent$ 树期望高度是 $\mathcal{O}(\log n)$ 级别的。 我们做题就是根据这些性质（当然还有我没提到的性质）来使用 $\sf SAM$ 的。此外，我们观察到其实本质上，$\sf SAM$ 相当于把所有后缀加入的 $\sf AC$ 自动机，只不过为了保证复杂度，极大压缩了信息。（因为所有后缀的所有前缀就是所有子串！）所以 $\sf AC$ 自动机能做的事人家 $\sf SAM$ 也能干，$\sf AC$ 自动机做不了的事，$\sf SAM$ 还能干。 #### 字符串匹配 应该不需要再把 $\sf AC$ 自动机那一套再说一遍了吧。 > [SP1812 LCS2 - Longest Common Substring II](https://www.luogu.com.cn/problem/SP1812) > > 给 $n$ 个字符串 $s_i$，求它们的最长公共子串。($1\le n\le 10,1\le |s_i|\le 10^5$) 考虑对第一个串建 $\sf SAM$，然后设 `slen[i]` 表示所有剩下的串中，以 `i` 结尾的前缀的最长匹配长度的最小值，则最终答案即 `max(slen[i])`。考虑对每个串的每个前缀，在 $\sf SAM$ 上跑匹配，得到匹配长度后与 `slen[i]` 取 $\min$ 即可。具体过程与 $\sf AC$ 自动机十分类似，不过由于我们没有 $\sf Trie$ 图那样的结构，所以只能一个个跳 $\sf fail$（有没有哥哥教育一下这个复杂度为啥是对的），跳到哪匹配长度就是那个状态内的最长子串。而最后如果匹配上了，匹配长度加一即可。时间复杂度大概是 $\mathcal{O}(n|s_i|)$。 代码：[$\tt code$](https://www.luogu.com.cn/paste/u8j5xu71)。 #### parent 树 对标刚刚 $\sf AC$ 自动机的 $\sf fail$ 树。不过由于这玩意还能当后缀树用，所以用处更大了。（好吧因为这玩意的信息压缩过了，所以用法几乎没啥交集） > [P3804 【模板】后缀自动机 (SAM)](https://www.luogu.com.cn/problem/P3804) > > 给出 $S$，求出它所有出现次数不为 $1$ 的子串的出现次数乘上子串长度的最大值。($1\le |S|\le 10^6$) 注意到，$\sf parent$ 树上父亲结点的 $\sf edp$ 是由若干不交的子结点并成的，所以我们可以用 `siz` 记录每个结点的 $\sf edp$ 大小，初始时只有前缀对应的状态的 `siz` 是 $1$，因为我们只确定它们的出现次数，然后在 $\sf parent$ 树上合并即可。时间复杂度 $\mathcal{O}(n)$。注意到，因为父子结点之间 `len` 的严格大小关系，我们还可以用 $\mathcal{O}(n)$ 的排序（比如基数排序）找到父子关系，做到同样的复杂度。 代码：[$\tt code$](https://www.luogu.com.cn/paste/e0gcoxc7)。 > [P4248 [AHOI2013]差异](https://www.luogu.com.cn/problem/P4248) > > 给出一个长为 $n$ 的字符串 $S$，令 $T_i$ 表示它以 $i$ 开头的后缀，求： > $$\sum_{1\le i<j\le n}\operatorname{len}(T_i)+\operatorname{len}(T_j)-2\times\operatorname{lcp}(T_i,T_j)$$ > 其中 $\operatorname{len}$ 表示字符串长度，$\operatorname{lcp}$ 表示最长公共前缀。($2\le n\le 5\times 10^5$) 前半部分非常好求，考虑后半部分，要求的是两两后缀的 $\operatorname{lcp}$ 长度和。考虑后缀树上，两个结点对应后缀的 $\operatorname{lca}$ 的深度，即为它们的 $\operatorname{lcp}$ 长度。而对应到 $\sf parent$ 树上，就是对应状态的 `len`，为 $\operatorname{lcp}$ 长度。用反串建出来 $\sf parent$ 树后统计子树内子树外的贡献即可。时间复杂度 $\mathcal{O}(n)$。（其实能发现，如果用正串搞，求出来的是 $\operatorname{lcs}$，最长公共后缀） 代码：[$\tt code$](https://www.luogu.com.cn/paste/s1r9bipb)。 当然，$\sf parent$ 树既然是一棵性质非常好的树，就一定能把树上算法（重剖，$\sf LCT$，点分治等）拿来套到这上面维护些什么。因为笔者很菜，所以还没做出来过这样的题，这里只扔一道例题。 > [P4482 [BJWC2018]Border 的四种求法](https://www.luogu.com.cn/problem/P4482) > > 给出一个字符串 $S$，$q$ 次区间询问 $\rm border$ 长度。($1\le |S|,q\le 2\times 10^5$) #### 动态规划 同 $\sf AC$ 自动机，只不过因为 $\sf SAM$ 建图的特殊性，拓扑序不再是编号顺序了，需要我们从根开始遍历。 > [P3975 [TJOI2015]弦论](https://www.luogu.com.cn/problem/P3975) > > 给出一个字符串 $s$，求出它的第 $k$ 小子串，分别对不同位置的相同子串算多个和算一个求解。($1\le |s|\le 10^5,1\le k\le 10^9$) 注意到一个子串对应的就是一条路径，所以如果我们能求出从一个结点出发有多少条路径，我们就能用类似 $\sf BST$ 上找第 $k$ 大的思路找到第 $k$ 小的子串了。首先考虑在 $\sf parent$ 树上合并出 $\sf edp$ 的大小 `siz`。然后就可以 $\rm dp$ 了，如果本质相同的子串算一个，那就是单纯的统计路径条数，如果算多个，那就要把点权设为 `siz` 再求和，因为 `siz` 的值就是这个 $\sf edp$ 内子串出现的次数。具体实现细节见代码。 代码：[$\tt code$](https://www.luogu.com.cn/paste/qd2z151d)。 > [CF700E Cool Slogans](https://www.luogu.com.cn/problem/CF700E) > > 给出一个字符串 $S$，要求构造出 $s_1,s_2,\cdots,s_k$，满足任意 $s_i$ 都是 $S$ 的子串，且 $\forall i\in[2,n]$，都有 $s_{i-1}$ 在 $s_i$ 中出现了至少两次。求出最大的 $k$。($1\le |S|\le 2\times10^5$) 注意到这个选择的关系，前一个必须在后一个中出现，而这在 $\sf SAM$ 的 $\sf parent$ 树上可以看成是父子关系，即 $s_{i-1}$ 必须是 $s_{i}$ 的祖先结点，且在 $s_i$ 中出现了两次。这就非常像树形 $\rm dp$ 了，考虑设 $f_i$ 表示走到 $i$ 号结点能得到的最大的 $k$，为了方便转移，并设 $g_i$ 表示 $i$ 号结点对应的最大的 $k$ 的结尾结点。（有可能 $i$ 选不上，所以要额外维护）则转移时，我们考虑接上父亲结点的 $g$，判断 $g_{fa_i}$ 对应的字符串是否在 $i$ 中出现两次，如果出现，则就接上这个最长 $k$： $$f_i=f_{fa_i}+1,g_i=i$$ 否则接不上： $$f_i=f_{fa_i},g_i=g_{fa_i}$$ 特别地，如果这个结点没有父结点，或父节点是根结点，则为边界条件： $$f_i=1,g_i=i$$ 最后答案为 $f_i$ 的最大值。发现整个过程中，我们唯一没办法用 $\sf SAM$ 的结构很方便维护的就是，判断一个子串是否在另一个中出现两次。这个要用到下文马上要说的，维护具体的 $\sf edp$ 集合。维护出来之后，找到每个结点任意一个 $\sf edp$ 值 $pos$。判断 $x$ 是否在 $y$ 中出现两次时，因为 $x$ 是 $y$ 的祖先（后缀），所以 $pos$ 处一定出现了一次，而剩下的一次，只需要出现在 $y$ 内就可以了，即判断 $x$ 有没有 $\sf edp$ 值位于这个区间： $$[pos-\operatorname{len}(y)+\operatorname{len}(x),pos)$$ 所有合并和查询的过程均可以用线段树合并实现，时间复杂度 $\mathcal{O}(n\log n)$。 代码：[$\tt code$](https://www.luogu.com.cn/paste/p37ss1f9)。 #### 维护具体的 edp 集合 发现 $\sf edp$ 集合的合并，完全可以用线段树合并做到维护 $\sf edp$ 集合里具体有哪些位置。而我们有了这个信息，那对于特定的字符串问题是无往而不利。 > [P4094 [HEOI2016/TJOI2016]字符串](https://www.luogu.com.cn/problem/P4094) > > 给出一个长为 $n$ 的字符串 $S$，和 $m$ 组询问，每组询问以 $(a,b,c,d)$ 描述，求出 $S_{a,b}$ 的所有子串与 $S_{c,d}$ 的 $\operatorname{lcp}$ 的最大值。($1\le n,m\le 10^5$) 这道题看起来很无从下手，但注意到答案满足单调性，所以考虑二分转化成判断性问题。现在问题变为，$S_{c,c+x-1}$ 是否在 $S_{a,b}$ 中出现过，这问题一下就可做了。首先注意到，$S_{c,c+x-1}$ 是前缀的形式，在 $\sf SAM$ 上不太好处理，考虑转化为后缀，即把原串反转，下文中的 $a,b,c,d$ 均指反转后的。然后我们拿出 $\sf parent$ 树，在上面做线段树合并，即把儿子的 $\sf edp$ 集合对应的值域线段树合并到父结点，初始时前缀所在的状态有值，为前缀的结束结点。然后如果我们能找到 $S_{d-x+1,d}$ 所在的状态，就可以通过查询这个状态的 $\sf edp$ 集合，是否在 $[a+x-1,b]$ 中有值来判断是否在 $S_{a,b}$ 中出现了。现在我们的问题是找到 $S_{d-x+1,d}$ 的状态。注意到如果我们记录前缀所在状态，则可以方便找到 $S_{1,d}$ 所在状态，然后从这个状态开始往根节点走，$\sf edp$ 集合越来越大，同时 `len` 值越来越小，当刚好 `len` 值满足大于等于 $x$ 时，我们就找到了这个状态。发现上面的过程很容易用树上倍增优化。总时间复杂度 $\mathcal{O}(n\log^2n)$。 代码：[$\tt code$](https://www.luogu.com.cn/paste/h5toe1tx)。 > [P4384 [八省联考 2018] 制胡窜](https://www.luogu.com.cn/problem/P4384) 我写过 [八省联考的总结](https://www.luogu.com.cn/blog/i-am-zhiyangfan/jiu-xing-lian-kao-2018-ti-xie)。 #### 广义 SAM $\sf SAM$ 的扩展版，把 $\sf SAM$ 搬到了 $\sf Trie$ 树上，从而把 $\sf SAM$ 能处理的领域又增加到了多串。注意，这里采用的方法是 $\rm bfs$ 离线建广义 $\sf SAM$。**不要学盗版做法。**（如果我的写假了也请提醒一声qwq） > [P6139 【模板】广义后缀自动机（广义 SAM）](https://www.luogu.com.cn/problem/P6139) > > 给出 $n$ 个字符串 $s_i$，求它们的本质不同子串个数。($1\le n\le 4\times 10^5,1\le \sum|s_i|\le 10^6$) 用板子题简单说说广义 $\sf SAM$ 的建立过程和性质吧。离线 $\rm bfs$ 建立，就是先把所有串插入 $\sf Trie$ 树内，然后再 $\rm bfs$ 整个 $\sf Trie$ 树，并用 $\sf Trie$ 树的结构来辅助广义 $\sf SAM$ 的建立。具体来讲，对于 $\sf Trie$ 树上的每个结点，我们额外维护 `fa` 表示它在 $\sf Trie$ 树上的父结点（这么说可能有点怪，反正就是转移指向它的那个状态），和 `ch` 表示 `fa` 到当前状态，对应转移的字符。$\rm bfs$ 到当前结点时，就用 `fa` 在 $\sf SAM$ 上对应的状态当 `las`，加入 `ch` 这个字符，并存储当前结点在 $\sf SAM$ 上对应的状态。初始时，$\sf Trie$ 树的根对应 $\sf SAM$ 的根。 建立完后，我们得到的广义 $\sf SAM$ 相当于是储存了加入的所有字符串的所有子串的信息，所有性质和普通的 $\sf SAM$ 都是相似的。不仅如此，我们还能额外给每个结点打上标记，表示它是来自哪个字符串的，从而实现更强的功能。（详见下一题）而对于本题，我们只需要求出每个状态能表示的状态和即可，也就是 `a[i].len - a[a[i].f].len`。时间复杂度 $\mathcal{O}(\sum |s_i|)$。 代码：[$\tt code$](https://www.luogu.com.cn/paste/id52mywg)。 > [P6793 [SNOI2020] 字符串](https://www.luogu.com.cn/problem/P6793) > > 给出两个长度均为 $n$ 的字符串 $a,b$，求它们所有长度为 $k$ 的子串，两两配对后，$\operatorname{lcp}$ 之和的最大值。($1\le k\le n\le 1.5\times 10^5$) 首先发现，两个串的 $\operatorname{lcp}$ 是后缀树上 $\operatorname{lca}$ 的深度，而两两配对时，我们有一个显然的贪心方法，那就是能在深处匹配上就在深处匹配上。所以如果我们能建出来一棵后缀树，并维护一个结点的子树内，分别有有多少结点属于 $a,b$，我们就能实现上述贪心过程。 考虑把 $a,b$ 的反串建起广义 $\sf SAM$，并在插入 $\sf Trie$ 树时，就把所有深度大于等于 $k$ 的结点打上它属于 $a$ 还是 $b$ 的标记，并在加入 $\sf SAM$ 时也一并继承过去。注意，标记在 $\sf Trie$ 树上有可能重叠，请注意处理。现在，我们就拥有了一个刚刚提到的后缀树，只需要 $\rm dfs$ 一遍，维护每个结点子树内还剩多少 $a,b$ 的结点能匹配，子树匹配完后合并上来它再匹配即可。时间复杂度 $\mathcal{O}(n)$。 代码：[$\tt code$](https://www.luogu.com.cn/paste/y94z0q7c)。 ### 回文自动机 回文自动机（也称作 $\sf PAM$，回文树）是一种能处理 **大部分回文串问题** 的 $\sf DFA$，它储存的是字符串的所有回文串信息。因为这东西好像不是特别被认可是标准的 $\sf DFA$，所以就不再介绍它的 $\sf DFA$ 要素了，干脆当做树介绍了。由于是回文，所以一定有奇回文和偶回文的区别，$\sf PAM$ 上，有两个根，奇根和偶根分别处理它们的信息。边表示从上一个状态两边加上两个字符。而奇根的长度是 $-1$，这保证第一次加字符仅会加 $1$ 个。除此之外，它还有后缀链接，类似的，连向最长的回文后缀。$\sf PAM$ 的状态数仅为 $\mathcal{O}(n)$，这是因为一个串最多有 $\mathcal{O}(n)$ 个本质不同回文串。建立过程 OI wiki 讲的挺详细的，这里仅给出 [板子题的代码](https://www.luogu.com.cn/paste/cbcq691m)。 没做过啥题，只有一道非板子题的介绍。 > [Palindromeness](https://vjudge.net/problem/CodeChef-PALPROB) > > 定义一个串的回文度： > - 如果这个串不是回文串，则回文度为 $0$。 > - 一个字符的回文度是 $1$。 > - 长度为 $x(x>1)$ 的字符串的回文度是它长度为 $\lfloor\frac{x}{2}\rfloor$ 的前缀的回文度加 $1$。 > > 给出一个字符串 $S$，求出它的所有非空子串的回文度之和。($1\le |S|\le 10^5$) 显然可以只考虑所有本质不同的回文串，把它们的回文度乘上出现次数。首先我们先来解决个子问题，求一个回文串的出现次数。 考虑 $\sf PAM$ 的插入过程，显然编号就是拓扑序，所以我们只需要逆序枚举所有状态，将当前状态的出现次数加入到 $\sf fail$ 指针对应状态的出现次数即可，毕竟它都出现了，后缀肯定出现了。初始状态可以在插入的时候求出。 现在我们的问题就是解决求一个回文串的回文度了。对于一个回文串，它的回文度就是长度为 $\lfloor\frac{x}{2}\rfloor$ 的前缀的回文度，考虑改成后缀，这是等价的。考虑按照拓扑序枚举结点，这样在处理当前结点时，如果长度为 $\lfloor\frac{x}{2}\rfloor$ 的回文后缀存在，那它的回文度一定被处理好了，可以直接计算当前状态的回文度。现在我们的问题变为了，判断一个回文串的长度为 $\lfloor\frac{x}{2}\rfloor$ 的后缀是否是回文，如果是，找出它在回文自动机上出现的位置。 注意到，这个问题可以很简单的通过爬 $\sf fail$ 树实现，只需要看看能不能找到长度为 $\lfloor\frac{x}{2}\rfloor$ 的结点即可。而根据 $\sf SAM$ 的经验，这个过程可以用树上倍增优化掉。所以最终时间复杂度 $\mathcal{O}(n\log n)$。 代码：[$\tt code$](https://www.luogu.com.cn/paste/i7tc7bqh)。