回文自动机（PAM）学习笔记

Update：2022.7.28。补充了对模板题解法的进一步说明，并对某些结论进行了补充或证明。 ## 前言 想必各位都学过 Manacher 算法（~~没关系，没学过不影响今天的内容~~）。不得不承认，Manacher 的确是处理回文问题 一个强力工具，可以在 $O(n)$ 的时间复杂度内求出一个字符串的最长回文子串。 但是，对于回文计数类问题（比如求一个字符串有多少个本质不同的回文子串），Manacher 就心有余而力不足了。所以，我们需要一个更为强大的数据结构处理这个问题。这就是今天的**回文自动机**（PAM）。 ## 概念 作为一个数据结构，首先需要明确回文自动机是个什么东西。 在开始之前，需要明确一些符号： - $s$：正在处理的字符串。默认下表从 $1$ 开始。 - $|s|$：字符串 $s$ 的长度。 - $s_{i\sim j}$：指 $s$ 从第 $i$ 位到第 $j$ 位组成的字串。 - $fa_u$：指在回文自动机中编号为 $u$ 的节点的父亲。 回文自动机是一棵树（因此也叫作回文树），它存的是一个字符串中的**所有回文子串** 的 **一半**。 而由于回文串又分奇回文和偶回文，所以回文自动机有两个根节点，$0$ 存的是长度为偶数的回文串，$1$ 存的是长度为奇数的回文串。 而它的每条边，代表一个字符 $c$，指的是从父节点所代表的字符串的头尾各加一个 $c$ 的到儿子所代表的字符串。 什么意思呢？我们不妨来看张图。 以字符串 $ababaababa$ 作例子。它的所有回文子串分别是： - 奇数：$a,b,aba,bab,ababa$； - 偶数：$aa,baab,abaaba,babaabab,ababaababa$。 它们建出来的回文自动机是这样的：  ~~有没有发现回文自动机和 Manacher 的关系很像 AC 自动机与 KMP 的关系，都是爸爸和儿子。~~ 从图中我们得到两个结论： - 除根节点外，每个节点恰好对应一个本质不同的回文子串，所以该树节点数 $-2$ 就是本质不同的回文子串个数（这很显然，原因跟 Trie 的储存原理是一样的，互不相同）。 - 若 $0$ 号节点对应字符串长度为 $0$，$1$ 号为 $-1$。则其余节点深度每 $+1$，所对应的回文串长度 $+2$（因为从下到上读一遍，又从上往下又读一遍）。 所以你现在知道为什么只存回文的一半了吧？除了节省空间，还是为了**避免本质相同的子串**。 ## 原理 现在我们来看看回文自动机是怎么工作的。 ### 插入新节点 这个地方我看其他讲解的的时候懵懵懂懂的，希望这里能讲明白。 我们考虑轮到 $s_i$ 插入时的情况。即前 $i-1$ 个字符都已经在树上了。 显然，加入该字符时肯定会出现若干个新的回文子串。那是不是要枚举所有新出现的回文子串呢？ 显然不是。回文串左右两边相等。当插入第 $s_i$ 时，除了最长的新回文子串，其它看似新增的回文子串，其实在 $s_i$ 之前就已经在里面了。 以下是不严谨的证明：首先我们需要明确，新增的所有回文子串必定是当前串的后缀（因为它们全都包含当前的 $s_i$，不然不叫新增）。也就是说，只要不包含 $s_i$ 的均不是新增的。如果新增的某个串（设为 $t$）不是最长子串（设为 $s$），即 $|t|\leq |s|$，那因为 $s$ 也是回文的，所以在以 $s_{i-|t|+1}$ 为结尾，长度为 $|t|$ 的子串必定是 $t$（可以理解为把 $t$ 以 $s$ 的回文中心为对称轴做对称）。而这个 $t'$ 明显不包含 $s_i$，所以并不是新增的。 说穿了，精髓就是长回文串一定包含短回文串。 所以回文自动机的空间复杂度是 $O(|s|)$ 的。 例如 $ababaababa$ 已经插入完了 $ababaab$，现在轮到插入 $a$，那真正没有出现过的只有 $abaaba$。其他的，比如说 $aba(s_{6\sim 8})$，在 $s_{3\sim 5}$ 就已经出现过了。 现在，我们就要考虑如何将 $abaaba$ 这个最长新回文子串插入到树上了。 首先，$abaaba$ 是由 $baab$ 从头尾分别添加 $a$ 得到的，而这个 $baab$ 肯定已经在树上了（插入 $s_7$ 时已经加到树上了）。那我们只要找到 $baab$ 对应的节点，直接连一条 $a$ 的边就完事了。 怎么找这个 $baab$ 呢？我敢肯定，这个 $baab$ 一定是 $s_{0\sim i-1}$ 中的最长回文后缀（不信你看是不是）。为什么呢？很简单，因为 $baab$ 是插入 $s_{i-1}$ 时新增的节点，肯定就是 $s_{i-1}$ 的最长回文后缀了。 那么，由这个“最长回文后缀”你想到了什么？ 没错，AC 自动机的 $fail$ 指针。所以，我们也定义一个类似 AC 自动机的 $fail_u$ 表示 $u$ 代表的**字符串的非自身最长回文后缀**。只要我们不停地眺，那 $fail_u,fail_{fail_u},\cdots$ 中总有一个可以在两边加上你要加的 $s_i$（即加上 $s_i$ 后仍为子串）（调到 $1$ 号根节点必定有解，后面会说）。然后看看合法点有没有 $s_i$ 这条边，如果有就直接往下走，没有就新建节点。 为什么是非自身？如果加上自身，它的 $fail$ 指针不就指向自己了？~~然后你的程序就会 T 成二臂……~~ 记 $len_p$ 为 $p$ 对应的回文子串长度。假设 $s_p$ 为以第 $i-1$ 位结束的最长回文子串的位置。当我们求 $ fail_i$ 时，合法的转移点就必须满足 $s_{p-len_p-1}=s_p$，这个与 AC 自动机寻找 $fail$ 指针的原理是一样的，只是变成了判断是否回文而已。 下面是完整的回文自动机的图：  最后一个问题：为什么 $fail_0=1$？有什么用？比如说当 $aaaaab$ 插入 $b$ 的时候，它的 $fail$ 怎么跳都是没用的（因为压根儿就没 $b$）。这时，$b$ 只能当做单个字符挂在 $1$ 的下面，而不能挂在 $0$ 的下面。因此，我们需要让 $fail_0$ 指向 $1$。至于 $fail_1$，不用管，用不到，因为单独一个字符也算回文，不可能在 $1$ 下失配的。 最后，后缀自动机的时间复杂度为 $O(|s|\log n)$（$n$ 为节点数量）。这是我自己的 ~~xjb~~ 分析：首先，$s$ 中的每个字符都要插入，所以至少是 $O(|S|)$。然后，对于每个字符，采用 $fail$ 指针一层一层向上跳（可以证明，$fail$ 连向的都是长度更小的，因为定义是非自身最长回文前缀），最多跳 $\log n$ 层（最坏情况就是每个 $fail$ 都指向它的父亲），所以最终就是 $O(|s|\log n)$ 的，十分优秀。 ## Solution 讲完原理，看看这道题怎么做：[P5496 【模板】回文自动机（PAM）](https://www.luogu.com.cn/problem/P5496)。 这题要求我们输出以字符串每个位置结尾的回文子串个数。因为回文自动机本身就涉及到后缀，所以要求结尾个数，只需要定义 $cnt_i$ 为以 $i$ 结尾的字符串的回文子串个数。更新的话，找到 $fail_i$ 后，$cnt_{fail_i}$ 就是除了 $i$ 之外的回文串数量。只要 $+1$（即加上哪一个新增的最长回文子串），就是 $cnt_i$ 的值。 ~~@管理员大大 这个题没啥好分析的吧，弄懂原理就很简单了。~~ 最后就是代码了，细节都在注释中。 ```cpp #include<bits/stdc++.h> using namespace std; const int N = 5e5 + 10; char s[N]; int n, lst, len[N]; int now, tot = 1, fail[N], cnt[N], t[N][26]; //tot 记得赋成 1，已经有两个根节点了 int getfail(int u, int p){//求 u 的fail指针 ，p表示当前插入的是哪个点 while(p - len[u] - 1 <= 0 || s[p - len[u] - 1] != s[p]) u = fail[u]; //如果当前位置比 u的回文串短或者字符不相等 就一直跳 return u;//最后不跳了，你就是答案了 } int insert(char c, int id){ int p = getfail(now, id);//找到那条路中有 id 位都一样的最长回文子串 //这个点就是他爸爸 if(!t[p][c - 'a']){//爸爸没它这个儿子，新认一个 fail[++tot] = t[getfail(fail[p], id)][c - 'a']; //fail等于((((爸爸的fail那条路上)有 id 位都是一样的回文串)的节点)的同名儿子) t[p][c - 'a'] = tot;//跟trie树一样 len[tot] = len[p] + 2;//长度等于爸爸+2 cnt[tot] = cnt[fail[tot]] + 1;//回文串数量等于fail的数量加上它自己 } return cnt[now = t[p][c - 'a']];//更新它现在的位置，并返回cnt作为答案 } int main(){ scanf("%s", s + 1); n = strlen(s + 1); fail[0] = 1, len[1] = -1; //len[i] 表示节点 i 所对应的回文串长度 for(int i=1;i<=n;i++){ if(i > 1) s[i] = (s[i] - 'a' + lst) % 26 + 'a'; printf("%d ", lst = insert(s[i], i)); } return 0; } ``` ~~这代码只能说一个字：短。~~ 秒完这题，大家也可以去看看 [P4287 双倍回文](https://www.luogu.com.cn/problem/P4287) 和其他一些比较基础的题目，加深理解。 到此结束吧，记得留下你们的赞哦！