回文自动机学习笔记

Wmd_125 · 2025-07-09 14:44:07 · 算法·理论

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

先做板题！

题意：对长度为 S 的字符串的每个位置求出以该位置结尾的回文串个数，强制在线。
1 \le S \le 5 \times 10^5

回文自动机，又称回文树，就是用来在线性时间解决这种回文串的问题的一类高效的工具。

下面我们来讲一下回文自动机的工作原理：

回文自动机 的工作原理类似于 AC自动机 ，都是运用前面求出的信息快速的求出新加入的字符的信息。

但不一样的是，回文自动机的每一个节点所代表的是半个回文串，这样不仅省空间，还能更快的判断是否有重复回文串。

但我们发现长度为奇数的回文串（下面简称奇串）和长度为偶数的回文串（下面简称偶串）的对称不太一样，所以我们开两个回文自动机，一个存奇串，一个存偶串，两个的根节点分别记为 1 和 0。

例如下图：

节点6所代表的回文串就是 BAB ，节点5所代表的回文串就是 ABBA。

相信你也发现了，一个节点所代表的回文串就是从这个节点走到根节点再走回来的路径上的字符集。

设回文树上的第 i 个点为 tr_i 。

我们考虑递推，假如我们前 i-1 个字符已经处理完了，我们现在加入第 i 个字符，该怎么办。

我们可以记一个指针 lt ，表示代表以第 i-1个字符为结尾的最长回文串的节点。因为你要找以 s_i 结尾的回文串，只要回文串长度不为 1 ，那么这个回文串一定包含字符 s_{i-1} 的。

假如说我们的运气非常好，新加入的 s_i 刚好可以和我们上一个回文串接上，那么我们就可以愉快的新建一个节点接在节点 tr_{lt} 上了。

但是我们容易发现，我们的运气经常不是很好，接不上，那怎么办？。

这时候，我们就要知道回文树的精髓了，fail指针！

其实自动机的 fail 指针都差不多，像 AC 自动机的 fail 指针记得就是最长的是原串的前缀的真后缀子串。

而回文树的 fail 指针也是如此，它指向的是最长的真回文后缀串的节点。

像刚刚上面的那张图，如果我们把 fail 指针当做边连出来的话，就长这样：

蓝边就表示的是 fail 指针，len 记的是该节点所记得回文串长度。

注意，0 节点的 fail 指针指向 1 节点，1 节点的 fail 指针指向 0 节点。

当我们接不上的时候，我们就可以跳 fail 指针，把以 s_{i-1} 结尾的回文子串一个个试，试到只能以本身作为回文串为止。

跳 fail 指针的时间复杂度可以借鉴 AC 自动机跳 fail 指针的时间复杂度，可以证明，是线性的。

好的，我们已经发现 fail 指针非常好用了，那么新建一个节点后怎么求该点的 fail 指针呢？

我们同样可以借鉴 AC 自动机建 fail 指针的思路，先从父节点的 fail 开始跳，跳到一个点就试，试到根节点为止。试到正确的点后就将它的 fail 指针指到这个点对应的儿子上就行了。这同样可以证明是线性时间复杂度。

图中黑色方框指的是 s_i 所接的回文串，红色方框是 fail 指针所指的回文子串，最后面的点代表字符 s_i ，前面的圈可以推出是和 s_i 相同的字符。由图可知前面一定出现过 fail 指针所指的回文子串，因此在回文树上，对应点一定是有对应儿子的，不然一定无法接到红色方框所圈的回文子串。

递推，一个个加入新节点，每加入一个新节点就先跳 fail 指针找到该接到哪个节点下，之后再跳父节点的 fail 算出该节点的 fail 。完结撒花！！！

不对，是不是忘记板题了？

其实板题就是用刚刚的方法在线建出一棵回文树，同时我们发现如果将 fail 指针单拿出来构成一棵树（不考虑 0 节点和 1 节点），答案就是 fail 树上对应点的深度（深度从 0 开始记）。然后就做完了。

洛谷P4287

GMOJ4752

回文树 - OI Wiki

回文自动机