回文自动机小记 更新于 2026/6/26 20:31:06 作者

command_block

1.基本元素与构造

• 回文串

  约定 $s_R$ 表示将字符串 $s$ 翻转形成的字符串。

  满足 $s=s_R$ 的字符串 $s$ 称之为回文串。

  本文编写历程时间跨度较大，由于前后习惯不同，可能混用大小写字母表示字符串。

• 回文自动机的基本元素

每个节点表示原串的一个回文子串，不同的节点表示的回文子串本质不同。

转移边表示给当前串左右同时加上某个字符。若有 $u\rightarrow v$ ，则称 $u$ 为 $v$ 的前驱， $v$ 为 $u$ 的后继（之一）。

$fail$ 边指向自己的最长回文后缀，不难发现 $fail$ 形成一棵有根内向树。

称从结尾在原串末尾的最长回文子串开始向上跳 $fail$ 得到的链为终止链，其在原串中对应着这样的一系列回文子串。

即原串的所有回文后缀。

• 回文自动机的经典构造方法

增量法构造，每次在原串末尾加入一个字符，不妨设为 $\rm x$。

考虑加入 $\rm x$ 后的新回文后缀，如下图 :

• 性质① 每次最多只会加入一个新的本质不同的回文串，且是所有回后缀中最长的。

  如图，红色串为最长回文后缀,绿色串为某个较短的回文后缀。

则根据回文的性质,绿色串必然在之前已经出现过了。

推论 ：本质不同的回文子串(回文自动机的点数)不超过 $|S|$。

现在，问题就是如何找到这个最长的新回文后缀。

对于每个新回文后缀，若在其两侧去掉一个 $\rm x$ ，就是一个旧的回文后缀。

考虑新出现的回文串(红色)，则绿色部分（前驱）为旧终止链中的某个串。

那么，可以暴力跳旧终止链，并检查对应回文串左侧是否恰好有一个 $\rm x$。

由于终止链上长度是由下而上递减的，一旦找到一个符合要求的点 $v$ ，即找到了最长的新回文后缀。

若这个 $v$ 已经有 $\rm x$ 出边，则表示该最长回文后缀已经在前面出现过，找出 $d:v\xrightarrow{\rm x}d$ ，本次终止链末尾即为 $d$。

否则，最长回文后缀是全新的，新建点 $u$ 装这个后缀，连一条 $v\xrightarrow{\rm x}u$ ，且 $u.len=v.len+2$。

还有一个问题是，该串的 $fail$ 指向的新次长回文后缀如何寻找。

可以顺着终止链继续找到旧的回文后缀 $v'$ 满足左边有一个 $\rm x$。

根据 性质① 的证明，新次长回文后缀在前面出现过，所以此时 $v'$ 必有 $\xrightarrow{\rm x}$ 出边。

找出 $u':v'\xrightarrow{\rm x}u'$ ,则 $u.fail=u'$。

• 复杂度证明

  每次加入字符时，只会新增一个点和一个转移，状态总量显然是 $O(n)$ 的。

  每次暴力跳终止链的复杂度令人怀疑，其实也是 $O(n)$ 的。

  设当前终止链长度为 $k$ ，若跳过 $d$ 步才找到 $u.fail$ ，则新的由 $u$ 开始的终止链长度为 $k-d+1$。

  终止链长度的消长相当于蜗牛爬杆，复杂度是正确的均摊 $O(n)$ 。

• 实现细节

  奇回文串的构造并不完全遵守“左右同时加上某个字符”的规则，中心字符是单独出现的。

  所以，需要建立奇偶两个根，规定奇根转移得出的都是奇回文串，偶根转移得出的都是偶回文串。

  对奇根采取特殊规则，走转移只会增加一个字符，即为某个奇回文串的重心字符。

  为了兼容，可以把奇根的 $len$ 置为 $-1$ （这样可以看作加入两个重叠的字符）。

  偶根的 $fail$ 为奇根 (奇根的限制比偶根少，若没有偶回文串，尝试一下奇回文串的最低要求 ： 单个字符) ，奇根的 $fail$ 指向自己。

  加入字符 $\rm x$ 的构造过程中，如果发现串没有新次短回文后缀，则意味着前面的串中根本没有字符 $\rm x$，此时将最长回文后缀（只有一个字符 $\rm x$） 的 $fail$ 置为偶根。

  可能父亲和出边到自己的点是同一个点，要注意赋值顺序问题。

  此外，为了避免越界，让字符串从 $1$ 开始标号，并把第 $0$ 个字符标记为 $-1$。

struct Node
{int t[26],f,len;}a[MaxN];
int tn,las;
char str[MaxN];
void ins(int k,int c)
{
  int p=las; //las是旧终止链的末端
  while(str[k-a[p].len-1]!=c)p=a[p].f;		//找到新最长回文后缀的前驱
    if (!a[p].t[c]){				//若新最长回文后缀是全新的
    int np=las=++tn,v;				//新建点 np 装新最长回文后缀，其为新终止链的末端
    for(v=a[p].f;str[k-a[v].len-1]!=c;v=a[v].f);//找到新次长回文后缀的前驱
    if (!a[v].t[c])a[np].f=2;			//找不到,则 fail 为偶根 (空回文串)
    else a[np].f=a[v].t[c];			//否则由前驱找到新次长回文后缀
    a[a[p].t[c]=np].len=a[p].len+2;
  }else las=a[p].t[c];				//若新最长回文后缀出现过，简单地更改终止链末端
}
void Init()
{a[1].len=-1;a[1].f=a[2].f=1;tn=las=2;}
//奇根为1 偶根为2

• 经典应用

• 本质不同回文串数

点数$-2$ (除去两个根)

• 各个回文子串的出现次数

构造过程中，每加入一个字符时，相当于把整条终止链的出现次数 $+1$ 。

那么我们把每次的终止链末尾权值 $+1$ ，最后在 $fail$ 树上求和即可。

实际操作中，由于编号大的点一定不会是编号小的点的父亲，不需要建立树，直接按照编号求和也可。

• P3649 [APIO2014]回文串

求出出现次数之后，乘上 $len$ 取 $\max$ 即可。

评测记录

• P5496 【模板】回文自动机（PAM）

本题相当于在线地询问终止链长度，记录 $dep$ 并递推。

评测记录

• P4287 [SHOI2011]双倍回文

注意到双倍回文串也是一个回文串，此题可以转化成对于每个回文串，判定是否能拆成两个相同的偶回文串。

可以从该点跳 $fail$ 找到自己的所有回文后缀。若有长度恰为 $len/2$ 的，则符合要求。

暴力跳复杂度显然不对劲。

建立 $fail$ 树，$dfs$ 时开一个桶记录到根的链中各个点的 $len$ ，对于每个点只需要查看桶中为 $len/2$ 的位置。

评测记录

• P4555 [国家集训队]最长双回文串

对于每个位置，记录在此结束和开始的最长回文串长度，然后拼接即可。

可以正反分别构造一次回文自动机来求出。

评测记录

• CF17E Palisection

可以转化为求不相交的回文串对子数。

枚举靠前的串的结尾位置 $i$ ，则靠后的串只需要在 $i$ 以后开始即可。

记录 $L[i]$ 为在 $i$ 开始的回文串个数, $R[i]$ 为结束。(即为终止链长度)

可以正反构造两次回文自动机来求出。

$\sum\limits_{i=1}^{|S|}R[i]\sum\limits_{j=i+1}^{|S|}L[j]$ 即为答案。

评测记录

• P5555 秩序魔咒

其实就是双串最长公共回文子串。

对两个串分别建立回文自动机，由于状态量很少，可以选取两个自动机相同的转移进行搜索，即可得到所有的公共回文子串。

评测记录

• P5685 [JSOI2013]快乐的 JYY

题意就是求两个字符串的相等回文子串对子数。

类似上一题，对同样的转移搜索，将对应节点的出现次数相乘求和。

评测记录

另一种做法是，先建立 $A$ 的 $\rm PAM$ ，然后用 $B$ 在上面跑匹配。

逐个加入 $B$ 中的字符，维护在 $A$ 中能匹配到的最长回文后缀。

注意，匹配的时候是双向扩展，除了检查自动机的出边外，还要检查 $B$ 串对应的两个字符是否相等。

若匹配到 $u$ 点，则可以视为包含到了所有 $u$ 的祖先，对次数的贡献就是这一条链的 $siz$ 和。

那么预先向下求和即可。

评测记录

• CF835D Palindromic characteristics 加强版

原题 $|S|\leq 5000$ ，利用 $\rm PAM$ 可以做到 $|S|\leq 5\times 10^6$。

记 $\rm PAM$ 中串 $u$ 长度不超过 $len/2$ 的最长回文后缀为 $u.half$。

在构造回文自动机的同时，若新产生的点为 $np$ ，且找到 $p\xrightarrow{\rm x}np$ ，那么先找到 $p.half$ ，然后向祖先跳直到能产生对应回文后缀为止(注意不能直接检查有无出边,就算有也可能只是前面的)。

此时出边指向的那个点就是 $u.half$。复杂度证明类似前面对终止链长度变化的分析。

记 $f[u]$ 表示回文串 $u$ 的阶数，有如下 $\rm DP$ :

$\begin{cases}f[u]=f[u.half]+1&(u.half.len=u.len/2)\\f[u]=1&(u.half.len<u.len/2)\end{cases}$

评测记录

• P4762 [CERC2014]Virus synthesis

能够发现,答案肯定是在某次 $2$ 操作之后暴力加字符得来的。

我们建立原串的回文自动机,然后分别求出每个(偶)回文子串 $S$ 的构造代价 $S$ ,原串的构造代价即为 $n+\min F[S]-len[S]$。

考虑如何构造一个回文串,不难发现,最优策略的最后一步操作一定是 $2$。

看看上一次的 $1$ 是怎么用的。

如果用在外面，则可以视为在两侧同时加了一个字符，则可以按照从后缀自动机的转移边来 $DP$。

转移为 $f[v]=\min(f[v],f[u]+1)\ (u\rightarrow v)$

如果用在里面，则必然先造好一个后缀，这里只需要考虑回文后缀。

设 $S$ 为目标， $T1,T2$ 为两个能够转移的回文后缀,若 $|T1|>|T2|$ 则 $T1$ 不劣于 $T2$。

也就是说，只需要考虑该串的 $half$ （长度不超过 $len/2$ 的最长回文后缀）。

证明 : $T$ 构造出半个 $S$ 的代价 : $F[T]+|S|/2-len[T]$

由于 $T2$ 是 $T1$ 的后缀,可以在 $T2$ 前面加字符得到 $T1$ ,则有 $F[T1]\leq F[T2]+len[T1]-len[T2]$

$\Rightarrow F[T1]-len[T1]\leq F[T2]-len[T2]$

$\Rightarrow F[T1]+|S|/2-len[T1]\leq F[T2]+|S|/2-len[T2]$ ,即为转移代价的大小关系,证毕。

评测记录

• 更多构造方式

• 复杂度非均摊的构造 & 可持久化

暴力跳终止链是经典构造算法复杂度需要依赖于均摊的重要原因。

回忆一下我们跳终止链是为了找什么，不难发现，在找“祖先中第一个左侧有字符 $\rm x$ 的节点”。

那么，不妨记 $u.tr[c]$ 表示 $u$ 的祖先中第一个左侧有字符 $\rm x$ 的节点。

若 $u$ 是 $v$ 的祖先，则 $v$ 继承 $u.tr$ ，并将自己左侧字符对应的 $tr$ 修改。

这样就不需要暴力跳终止链了，然而由于需要复制数组，复杂度是 $O(n\Sigma)$ 的。

若使用可持久化数组，即可实现快速创建副本，复杂度变为 $O(n\log \Sigma)$ ，也可以支持可持久化。

• 两侧同时插入

考虑维护 $fail'$ 指针表示自动机中串的最长回文前缀。由回文，不难发现回文前缀同时也是回文后缀，所以总有 $fail'=fail$ ，不必额外维护。

所以，只需要记下正反两条终止链的末端就可以实现两侧插入了。

注意，当整个串变成回文串的时候，要更新另一侧的末端。

具体的讨论和实现请见例题 ： HDU5421 Victor and String | Sol

2.回文 $\bf Border$ 理论

需要先在 Border理论小记 学习前置芝士。

• 定理① 回文串的回文后(前)缀与其 $\rm Bd$ 对应。

证明 : 设串长为 $n$。长度为 $l$ 的回文后缀 $\Leftrightarrow\rm S[n-i+1]=S[n-l+i]=S[l-i+1]$

$\Leftrightarrow S[n-l+i-1]=S[i]\Leftrightarrow\rm$ 长度为 $l$ 的 $\rm Bd$。

图解如下，其中 $u,v$ 均为回文串，$v$ 是 $u$ 的后缀。

$\large\begin{aligned} &\qquad\qquad\boxed{\qquad\qquad\qquad v \qquad\qquad\qquad} \\&\boxed{\qquad\qquad\qquad\qquad u \qquad\qquad\qquad\qquad} \\&\boxed{\qquad\qquad\qquad {\normalsize{\large v}_R}\ \ \ \quad\qquad\qquad} \end{aligned}$

由于回文的定义 $v_R=v$ ，显然 $v$ 是 $u$ 的 $\rm Bd$。

推论 ：某个串的回文后(前)缀长度可以拆分为 $O(\log n)$ 个等差数列。

• 定理② 若回文串 $s$ 有周期 $p$，则一个循环节必然可以被拆成两个回文串，且长度分别为 $|p|-(s\bmod p),(s\bmod p)$。

设回文串 $s$ 的长度为 $n$，循环节为 $t$，周期为 $p=|t|$。

将 $s$ 表示成 $s=t^{k}t_1$ ，其中 $t_1$ 是 $t$ 的严格前缀。令 $t=t_1t_2$。有图 ：

$\begin{aligned} &\qquad\qquad\qquad\quad\ \ \boxed{\quad{t}_1\quad}\boxed{\quad\ \,t_{2}\,\ \quad} \\&\boxed{\qquad\quad\ t_{}\ \quad\qquad}\boxed{\qquad\quad\ t_{}\ \quad\qquad}\boxed{\quad{t}_1\quad} \\&\boxed{\qquad\qquad\qquad\qquad\,\ \ s\ \ \ \qquad\qquad\qquad\qquad} \\&\qquad\qquad\qquad\qquad\qquad\ \ \ \,\boxed{\qquad\quad t_R \quad\qquad} \end{aligned}$

由上图可得 $t_R=t_1t_2$ ，且显然有 $t_R={t_2}_R{t_1}_R$ ，可得 $t_1,t_2$ 均为回文串。不难发现 $t_1,t_2$ 的长度恰为 $s-(s\bmod p),(s\bmod p)$。

• 定理③ 设 $v$ 为回文串 $u$ 的最长回文严格前(后)缀，若 $2|v|\geq |u|$ ，那么 $v$ 只会在 $u$ 中恰好匹配两次，分别作为前缀和后缀。

  证明 : 由 定理① ，显然有这两次匹配，我们需要证明没有其他的匹配。

取出前两次匹配 $v_1,v_2$ ，假设 $v_2$ 不是后缀。

由 $\rm Border$ 论， $2|v|\geq u\Rightarrow\ v$ 在 $u$ 的匹配位置成一个等差序列，且公差为 $v$ 的周期。

匹配情况如图 ：

$\begin{aligned} &\boxed{\qquad\qquad\qquad\qquad\,\ \ u\ \ \ \qquad\qquad\qquad\qquad} \\&\boxed{\qquad\qquad v_{1}\quad|\quad\qquad} \\&\qquad\qquad\qquad\ \boxed{\qquad\qquad v_{2}\quad|\quad\qquad} \end{aligned}$

根据 定理② ，改写 $v$ 的循环节为两个回文串 $p_1,p_2$ ，则 $v=(p_1p_2)^kp_1$。

$\begin{aligned} &\boxed{\qquad\qquad\qquad\qquad\,\ \ u\ \ \ \qquad\qquad\qquad\qquad} \\&\boxed{\quad p_1\quad}\boxed{\ \ p_2\ \ }\boxed{\quad p_1\quad} \\&\qquad\qquad\qquad\ \boxed{\quad p_1\quad}\boxed{\ \ p_2\ \ }\boxed{\quad p_1\quad} \end{aligned}$

此时不难发现 $v_1∪v_2=(p_1p_2)^{2k}p_1$ 可以形成比 $v$ 更长的回文前缀，矛盾。

• 应用方式 :

  具体应用中，为了利用 定理③，对于划分出的一个回文后缀长度等差序列 $\{a_1,a_2,...,a_i,a_{i+1},...,a_m\}$ ，若 $i$ 是第一个不满足 $2|a_i|\geq |a_{i+1}|$ 的，则从 $a_i$ 处断开成两个等差序列分别处理。

  好处是，同一个等差序列的相邻串之间一定满足 定理③。

  不难发现此时仍然能把回文后缀长度（终止链）分成 $O(\log n)$ 段序列。

• 例题 ：

  • HDU6320 Cut The String | Sol

  • Loj#6681. yww 与树上的回文串 | Sol

  • CF932G Palindrome Partition | Sol

  • Loj#6070. 「2017 山东一轮集训 Day4」基因 | Sol