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

· · 题解

Update：2022.7.28。补充了对模板题解法的进一步说明，并对某些结论进行了补充或证明。

前言

想必各位都学过 Manacher 算法（没关系，没学过不影响今天的内容）。不得不承认，Manacher 的确是处理回文问题 一个强力工具，可以在 O(n) 的时间复杂度内求出一个字符串的最长回文子串。

但是，对于回文计数类问题（比如求一个字符串有多少个本质不同的回文子串），Manacher 就心有余而力不足了。所以，我们需要一个更为强大的数据结构处理这个问题。这就是今天的回文自动机（PAM）。

概念

作为一个数据结构，首先需要明确回文自动机是个什么东西。

在开始之前，需要明确一些符号：

回文自动机是一棵树（因此也叫作回文树），它存的是一个字符串中的所有回文子串 的 一半。

而由于回文串又分奇回文和偶回文，所以回文自动机有两个根节点，0 存的是长度为偶数的回文串，1 存的是长度为奇数的回文串。

而它的每条边，代表一个字符 c，指的是从父节点所代表的字符串的头尾各加一个 c 的到儿子所代表的字符串。

什么意思呢？我们不妨来看张图。

以字符串 ababaababa 作例子。它的所有回文子串分别是：

它们建出来的回文自动机是这样的：

有没有发现回文自动机和 Manacher 的关系很像 AC 自动机与 KMP 的关系，都是爸爸和儿子。

从图中我们得到两个结论：

所以你现在知道为什么只存回文的一半了吧？除了节省空间，还是为了避免本质相同的子串。

原理

现在我们来看看回文自动机是怎么工作的。

插入新节点

这个地方我看其他讲解的的时候懵懵懂懂的，希望这里能讲明白。

我们考虑轮到 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）。

这题要求我们输出以字符串每个位置结尾的回文子串个数。因为回文自动机本身就涉及到后缀，所以要求结尾个数，只需要定义 cnt_i 为以 i 结尾的字符串的回文子串个数。更新的话，找到 fail_i 后，cnt_{fail_i} 就是除了 i 之外的回文串数量。只要 +1（即加上哪一个新增的最长回文子串），就是 cnt_i 的值。

@管理员大大 这个题没啥好分析的吧，弄懂原理就很简单了。

最后就是代码了，细节都在注释中。

#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 双倍回文 和其他一些比较基础的题目，加深理解。

到此结束吧，记得留下你们的赞哦！