专栏文章

回文自动机学习笔记

WWmd_125
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioy2syr
此快照首次捕获于
2025/12/03 03:01
3 个月前
此快照最后确认于
2025/12/03 03:01
3 个月前
查看原文

回文自动机学习笔记

比赛 T1 有这么这么一道回文自动机上 DP 的题，虽然这道题可以暴力+剪枝硬跑过去，但本着改题要用最优解的思想，我们还是花了半个晚上+半个早上学习了回文自动机。

【模板】回文自动机(PAM)

先做板题！
题意：对长度为 SS 的字符串的每个位置求出以该位置结尾的回文串个数，强制在线。
1≤S≤5×1051 \le S \le 5 \times 10^5
回文自动机，又称回文树，就是用来在线性时间解决这种回文串的问题的一类高效的工具。
下面我们来讲一下回文自动机的工作原理：

工作原理

回文自动机 的工作原理类似于 AC自动机 ，都是运用前面求出的信息快速的求出新加入的字符的信息。
但不一样的是，回文自动机的每一个节点所代表的是半个回文串，这样不仅省空间，还能更快的判断是否有重复回文串。
但我们发现长度为奇数的回文串（下面简称奇串）和长度为偶数的回文串（下面简称偶串）的对称不太一样，所以我们开两个回文自动机，一个存奇串，一个存偶串，两个的根节点分别记为 11 和 00。
例如下图：
节点6所代表的回文串就是 BABBAB ，节点5所代表的回文串就是 ABBAABBA。
相信你也发现了，一个节点所代表的回文串就是从这个节点走到根节点再走回来的路径上的字符集。

建树

设回文树上的第 ii 个点为 tritr_i 。
我们考虑递推，假如我们前 i−1i-1 个字符已经处理完了，我们现在加入第 ii 个字符，该怎么办。
我们可以记一个指针 ltlt ，表示代表以第 i−1i-1个字符为结尾的最长回文串的节点。因为你要找以 sis_i 结尾的回文串，只要回文串长度不为 11 ，那么这个回文串一定包含字符 si−1s_{i-1} 的。
假如说我们的运气非常好，新加入的 sis_i 刚好可以和我们上一个回文串接上，那么我们就可以愉快的新建一个节点接在节点 trlttr_{lt} 上了。
但是我们容易发现，我们的运气经常不是很好，接不上，那怎么办？。
这时候，我们就要知道回文树的精髓了，fail指针！

failfail指针

其实自动机的 failfail 指针都差不多，像 ACAC 自动机的 failfail 指针记得就是最长的是原串的前缀的真后缀子串。
而回文树的 failfail 指针也是如此，它指向的是最长的真回文后缀串的节点。
像刚刚上面的那张图，如果我们把 failfail 指针当做边连出来的话，就长这样：
蓝边就表示的是 failfail 指针，lenlen 记的是该节点所记得回文串长度。
注意，00 节点的 failfail 指针指向 11 节点，11 节点的 failfail 指针指向 0 节点。
当我们接不上的时候，我们就可以跳 failfail 指针，把以 si−1s_{i-1} 结尾的回文子串一个个试，试到只能以本身作为回文串为止。
跳 failfail 指针的时间复杂度可以借鉴 ACAC 自动机跳 failfail 指针的时间复杂度，可以证明，是线性的。
好的，我们已经发现 failfail 指针非常好用了，那么新建一个节点后怎么求该点的 failfail 指针呢？
我们同样可以借鉴 ACAC 自动机建 failfail 指针的思路，先从父节点的 failfail 开始跳，跳到一个点就试，试到根节点为止。试到正确的点后就将它的 failfail 指针指到这个点对应的儿子上就行了。这同样可以证明是线性时间复杂度。

一些问题

  • Q：会不会存在在计算新加入的点的 failfail 指针时，发现对应点后没有对应的儿子的情况？
  • A：不会。如下图：
图中黑色方框指的是 sis_i 所接的回文串，红色方框是 failfail 指针所指的回文子串，最后面的点代表字符 sis_i ，前面的圈可以推出是和 sis_i 相同的字符。由图可知前面一定出现过 failfail 指针所指的回文子串，因此在回文树上，对应点一定是有对应儿子的，不然一定无法接到红色方框所圈的回文子串。
  • Q：回文串重复了会怎么样？
  • A：不会怎么样，可以发现回文串重复的话，failfail 指针是不会变的。

总结

递推，一个个加入新节点，每加入一个新节点就先跳 failfail 指针找到该接到哪个节点下，之后再跳父节点的 failfail 算出该节点的 failfail 。完结撒花！！！
不对，是不是忘记板题了？
其实板题就是用刚刚的方法在线建出一棵回文树，同时我们发现如果将 failfail 指针单拿出来构成一棵树（不考虑 0 节点和 11 节点），答案就是 failfail 树上对应点的深度 （深度从 00 开始记）。然后就做完了。

例题

洛谷P4287
GMOJ4752

参考资料

回文树 - OI Wiki
回文自动机

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...