回文自动机(Palindromic Tree)

回文自动机(Palindromic Tree),简称 eertree 或回文树,是一种专门用于处理回文子串的字符串数据结构。它能在逐字符加入字符串的过程中,在线维护出该串包含的所有本质不同回文子串,并支持统计每个回文串的出现次数、长度等信息。

概述

一个长度为 n 的字符串本质不同的回文子串数量不超过 n,这一线性性质是回文自动机高效的基础。该结构由回文树的发明者 Mikhail Rubinchik 提出,它把每个本质不同的回文子串对应为树上一个节点,并通过失配指针连接较短的回文后缀,兼具自动机与树的特征。

核心原理

• 节点表示:每个节点对应一个回文子串,记录其长度;节点间的转移边表示在回文串两端各添加一个相同字符。
• 两个根:分别代表长度为负一和长度为零的虚拟回文串,便于统一处理奇数长度和偶数长度的回文。
• 失配链接:每个节点有一条指向其最长回文后缀节点的指针,插入新字符时沿失配链寻找可扩展的回文。
• 在线增量:每次追加一个字符,从上一个最长回文后缀出发跳失配链,找到位置后新建至多一个节点,均摊为常数或对数复杂度。

整体构建时间与字符串长度成线性关系(在固定字符集下),空间也为线性。

应用场景

回文自动机可用于统计字符串中本质不同回文子串的个数、每个回文子串的出现次数、最长回文子串以及回文划分等问题。相比 Manacher 算法只求回文半径,回文自动机能保存回文串的结构关系,适合更复杂的统计任务。

常见问题

问:回文自动机和 Manacher 算法怎么选择?答:若只需求最长回文子串或回文半径,Manacher 更简单;若要统计本质不同回文子串及其出现次数、做回文相关的动态规划,则回文自动机更合适。

问:为什么需要长度为负一的根?答:它作为奇数长度回文的扩展起点,使单字符也能被视为在空串两端加字符得到,统一了奇偶长度的处理逻辑。