回文自动机 PAM 学习笔记

回文自动机

zeb 于 2026.2.2 讲解，做一个笔记。
1. 引入

回文树，或者说，回文自动机 PAM（Palindromic Automaton），是一种可以存储一个串中所有本质不同回文子串的数据结构。
由于这个算法就是从其它字符串相关自动机借鉴而来，因此于其它自动机有许多相似之处。在这个回文自动机中，每一个状态（即节点）都对应了原串中的一个子串。而不同的是，转移边上的字符，指的是在原状态上两侧分别加上一个这个字符，所形成的回文子串。
例如

你就会发现一个问题，我们这样只能得到偶数长度的子串，那该怎么办呢？也像 \(\text{Manacher}\) 那样加入间隔字符？
我们考虑一个巧妙而快捷的方法——我们建两棵根，一个是奇根，下面挂所有长度为奇数的回文子串；一个是偶根，下面挂所有长度为偶数的回文子串。
2. 构造

对每个状态，我们会储存以下内容：

• 对应字符串长度 \(\mathtt{len_u}\)；
  
• 对应字符串所有出边指向的结点 \(\mathtt{trie_{u,c}}\)；
  
• 状态的失配指针 \(\mathtt{fail_u}\)（含义在下文）。
  

对于奇根和偶根，我们分别定义它们的长度为 \(-1\) 和 \(0\)。这样可以保持统一性，在一个状态后加入一个后继状态时，它所对应的长度就直接设为它父亲长度加 \(2\) 即可。
对于 \(\text{PAM}\) 的构造，我们类似于 \(\text{SAM}\) 采用增量构造，即每加入一个字符，我们都可以实时更新这个回文自动机。
那么，不妨设我们现在要加入的这个点是第 \(i\) 个字符，前 \(i-1\) 个字符对应的 \(\text{PAM}\) 已经构造好。
我们考虑加入这个字符串会产生的新的回文子串，即以第 \(i\) 位为结尾的回文子串。在这么多的回文子串中，我们每个都要新建节点吗？并非，事实上，我们只需要新建最长的一个后缀回文子串对应状态即可。因为可以保证，比它短的以前一定已经出现过了，比如说这个例子：
对于子串 \(\mathtt{abaccaba}\)，后缀回文子串共有三个，\(\mathtt{abaccaba,aba,a}\)。
其中你会发现，如果一个后缀回文子串不是最长的，那么它一定可以被最长的那一个后缀回文子串翻转过去，比如说这里的 \(\mathtt{aba}\)，就可以通过整个子串找到一个对称位置上同样的 \(\mathtt{aba}\)，这也就是为什么我们至多只需要新建最长回文后缀对应节点就可以了。
现在我们的任务，就是找到这个新节点该建立在哪里。你会发现，这个节点的父亲，即将这个最长回文后缀掐头去尾，一定也是一个回文串，且就是 \(i-1\) 位置上的一个后缀回文子串。于是这个任务就转化成了，找到一个对应子串最长的节点 \(u\) 满足

• 它对应的子串是 \(i-1\) 的一个后缀回文子串；
  
• \(s_{i-\mathtt{len_u}-1}=s_i\)。
  

我们记录 \(i-1\) 位置最长回文后缀对应状态节点编号为 \(\mathtt{last}\)。如果这个节点已经满足这个条件了，很好，我们直接把新节点连在 \(\mathtt{last}\) 下面即可。但如果不行呢？因此，我们这里类似 \(\text{ACAM}\)，引入 \(\text{Fail}\) 失配指针。\(\mathtt{fail_u}\) 表示的含义是，状态 \(u\) 对应的回文子串的最长回文后缀对应的状态。
那么可以发现，\(\mathtt{last},\mathtt{fail_{last}},\mathtt{fail_{fail_{last}}},\dots\) 就对应了以 \(i-1\) 结尾的所有后缀回文子串！
因此在这里，我们只需要不断往上跳 \(\text{Fail}\) 指针即可。那么如果一直找都找不到，怎么办？这时候我们考虑把偶根的 \(\mathtt{fail_0}\) 连到奇根上去。这样跳 \(\text{Fail}\) 时，由于奇根的 \(\mathtt{len_1}=-1\)，因此 \(i-\mathtt{len_1}-1=i\)，即对于 \(s_i\) 这个单字符的回文串，二条件一定成立，很自然的就会连到奇根下面。这一方面揭示了设奇根长度为 \(-1\) 的另一好处，同时也说明了，为什么 \(\mathtt{fail_0}\leftarrow 1\)。
那么找到了父亲，我们接下来就是要为这一点也连一条 \(\text{Fail}\) 指针出去。
其实也很简单，这条 \(\text{Fail}\) 指针，连向的其实就是以 \(i\) 结尾的第二长的回文后缀。那么我们只需要继续从 \(\mathtt{fail_{last}}\) 开始跳，再找到第一个符合二条件的就可以了。
下面是实现。
[code]int last,tot=1,fail[N],len[N],trie[N][30];//last 最开始挂在偶根//tot 记得要赋初值为 1int getfail(int u,int id){    while(s[id]!=s[id-len-1]) u=fail; //不满足二条件就一直跳    return u;}void pamConstruct(){    fail[0]=1,len[1]=-1;    //初始化 偶根的 fail 指向奇根，奇根的长度为 -1    for(int i=1;i>s; n=s.length();        s=" "+s;        fail[0]=1,len[1]=-1;        for(int i=1;i>c; s[++R]=c;                                insert(c,R,suf,1);                        }                        else if(op==3) cout