信奥新赛季进入冲刺阶段字符串算法是各大省级、校级 C 上机赛的常客。前面我们聊过后缀自动机、后缀数组、多模式串匹配今天把字符串四剑客的最后一位补齐——回文自动机Palindrome Automaton也叫回文树 Eertree。它能在线性的时间里把字符串里所有的镜像片段回文子串一次性梳理清楚本质不同回文子串有多少个、最长的是多长、每个回文串出现了几次。比起马拉车Manacher只能求最长回文半径回文自动机还多了一层计数的本领是处理回文统计类题目的利器。一、原创题校园广播台听写回文挑战校园广播台每天播放一段由小写字母组成的镜像诗编辑想知道这段内容里藏了多少个回文片段。给定字符串S仅含小写字母|S| ≤ 10^5请回答三个问题问题一S中有多少个本质不同的回文子串镜像片段问题二其中最长的回文子串长度是多少问题三所有回文子串可重叠计数一共出现了多少次即回文子串的总数示例S ababa- 本质不同回文子串a、b、aba、bab、ababa→5 个- 最长回文子串长度5- 回文子串总数a×3 b×2 aba×2 bab×1 ababa×1 9二、核心考点拆解回文自动机的精髓是建两棵树让每个节点代表一个本质不同的回文子串。双根结构维护两个虚根——节点0是偶数长度回文的根len0节点1是奇数长度回文的根len-1。真实回文节点从2号开始因此本质不同回文个数 节点总数 − 2。节点含义每个节点u存len[u]该回文长度、fail[u]最长真回文后缀指针类似后缀自动机的后缀链接、ch[u][c]在左右各加字符c后跳转到的节点、cnt[u]出现次数。get_fail跳链给定当前位置i和节点x沿fail向上跳直到S[i]与S[i − len[x] − 1]相等——也就是说x代表的回文串左右各加一个S[i]后仍是回文。extend增量插入逐字符插入。若ch[x][S[i]]已存在说明该回文早已建好仅把出现次数1否则新建节点len len[x] 2并算出它的fail。fail的计算新节点的fail指向去掉首尾字符后最长的回文后缀通过get_fail(fail[x], i)找到后再取其字符c的转移单字符回文len1的fail固定指向偶根0空串。出现次数上推插入时只在以i结尾的最长回文节点上1构建完成后按节点编号从大到小沿fail累加cnt[fail[u]] cnt[u]即可得到每个回文串的总出现次数——任何回文串的出现次数等于它作为后缀结尾的位置数。三、解法实现C / Python 双版C 版本#include iostream #include string #include vector #include array #include algorithm using namespace std; struct PAM { int tot, last; vectorint len, fail, cnt; vectorarrayint, 26 ch; string s; void init() { tot 2; last 0; // 节点 0偶根(len0), 1奇根(len-1) len.assign({0, -1}); fail.assign({1, 0}); cnt.assign({0, 0}); ch.assign(2, arrayint, 26{}); // 两个零填充数组 s.clear(); } int getfail(int x, int i) { while (i - len[x] - 1 0 || s[i - len[x] - 1] ! s[i]) x fail[x]; return x; } void extend(int c, int i) { int x getfail(last, i); if (ch[x][c]) { // 该回文已存在仅计一次出现 last ch[x][c]; cnt[last]; return; } int cur tot; // 新建节点 len.push_back(len[x] 2); cnt.push_back(1); ch.push_back(arrayint, 26{}); if (len[cur] 1) // 单字符回文最长真后缀是空串偶根 fail.push_back(0); else { int y getfail(fail[x], i); fail.push_back(ch[y][c]); } ch[x][c] cur; last cur; } void build(const string str) { init(); for (int i 0; i (int)str.size(); i) { s str[i]; extend(str[i] - a, i); } } int distinct() { return tot - 2; } // 去掉两个虚根 int longest() { int mx 0; for (int i 2; i tot; i) mx max(mx, len[i]); return mx; } long long total_occurrence() { // 沿 fail 把出现次数上推 for (int i tot - 1; i 2; --i) cnt[fail[i]] cnt[i]; long long sum 0; for (int i 2; i tot; i) sum cnt[i]; return sum; } }; int main() { PAM pam; string s ababa; pam.build(s); cout pam.distinct() pam.longest() pam.total_occurrence() \n; // 输出5 5 9 return 0; }Python 版本class PAM: def __init__(self): self.len [0, -1] # 节点 0偶根, 1奇根 self.fail [1, 0] self.ch [dict(), dict()] self.cnt [0, 0] self.tot 2 # 下一个节点编号 self.last 0 self.s [] def get_fail(self, x, i): while i - self.len[x] - 1 0 or self.s[i - self.len[x] - 1] ! self.s[i]: x self.fail[x] return x def extend(self, c, i): x self.get_fail(self.last, i) if c in self.ch[x]: # 该回文已存在仅计一次出现 self.last self.ch[x][c] self.cnt[self.last] 1 return cur self.tot self.tot 1 self.len.append(self.len[x] 2) self.cnt.append(1) self.ch.append(dict()) if self.len[cur] 1: # 单字符回文最长真后缀是空串 self.fail.append(0) else: y self.get_fail(self.fail[x], i) self.fail.append(self.ch[y][c]) self.ch[x][c] cur self.last cur def build(self, s): self.s list(s) for i, ch in enumerate(self.s): self.extend(ch, i) def distinct(self): return self.tot - 2 def longest(self): return max(self.len[2:]) if self.tot 2 else 0 def total_occurrence(self): # 沿 fail 上推出现次数 for i in range(self.tot - 1, 1, -1): self.cnt[self.fail[i]] self.cnt[i] return sum(self.cnt[2:]) pam PAM() pam.build(ababa) print(pam.distinct(), pam.longest(), pam.total_occurrence()) # 5 5 9四、时间与空间复杂度时间复杂度get_fail沿fail跳链结合势分析整个构建过程是均摊O(n)的每个字符均摊常数步。total_occurrence的拓扑累加是 O(节点数) O(n)。整体O(n)。空间复杂度本质不同回文子串个数最多为 n 个每个节点存len/fail/cnt和 26 个转移空间O(n·|Σ|)Σ 为字符集大小。字母表固定 26 时即 O(n)。五、六个高频易错点双根初始化len必须是[0, -1]fail是[1, 0]tot从2起步。fail[0]1保证偶根跳空后落到奇根fail[1]0是奇根的兜底。get_fail的越界判断i − len[x] − 1 0必须先判否则访问s[-1]越界。这是回文自动机最常见的段错误来源。单字符回文的特殊faillen1的新节点fail要显式指向 0偶根不能走通用公式否则会得到指向自身的错误后缀链接。fail拓扑顺序出现次数上推必须按节点编号从大到小遍历fail[u] u恒成立从小到大会漏算。本质不同回文个数 tot − 2两个虚根不算真实回文千万别漏减 2也不要把空串偶根算进去。字符集与数组大小用固定int ch[N][26]时要确保N足够若图省事用vector则天然无上限但要注意别把大数组塞进栈上分配会爆栈应放在堆或全局。六、进阶拓展每个回文串的出现次数total_occurrence执行完后cnt[u]就是节点u代表回文的出现次数可直接回答某个回文出现了几次。洛谷 P5496模板求以每个位置结尾的回文子串个数答案正是extend时当前last节点被累加前的cnt值或构建后再查cnt[last]。最长双回文串洛谷 P4287对每个位置分别向左、向右求以该位置为对称中心、作为左半或右半的最长回文拼接得到前后都是回文的最长串是fail树与左右扫描的经典应用。广义回文自动机多串建树时插入新串前要重置last并把s清空若两串交界处出现重复回文需要小心处理cnt的归属。与马拉车Manacher对比Manacher 用O(n)直接给出每个中心的最长回文半径常数更小回文自动机的优势在于能计数本质不同个数、每个回文出现次数二者互补按题目需求选用。七、小结与互动回文自动机用一个两棵树 后缀链接的优雅结构把回文子串的枚举、去重、计数一次性在线性时间内解决。记住三条主线双根建树、get_fail跳链找对称位置、fail拓扑上推统计次数再配合上面的六个易错点就能稳稳拿下这类字符串题。你在校内 C 训练或模拟赛里做过哪些回文相关的题目是求最长回文、数回文个数还是双回文拼接欢迎在评论区聊聊我们下一期可以继续深挖回文自动机在本质不同回文 × 出现次数上的变式题。 免费少儿编程资料夸克网盘领取以下资料来自夸克网盘分享点击链接可直接保存若需在 App 内打开也可复制下方明文链接全国青少年信息素养大赛复赛集训题目PythonC.docxhttps://pan.quark.cn/s/93995d3cb1502024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdfhttps://pan.quark.cn/s/da97b5dbf75dPython背记手册.pdfhttps://pan.quark.cn/s/7568ae9ca92bPython课程https://pan.quark.cn/s/a94bf02d00c62024信息素养大赛图形化复赛集训题答案3-9https://pan.quark.cn/s/6ccab7ec3cbc2025年03月份电子学会考级真题https://pan.quark.cn/s/4403c42289122025全国青少年信息素养大赛赛项说明https://pan.quark.cn/s/d9d0df4a9f29青少儿信息素养大赛编程资料https://pan.quark.cn/s/4ab6bd83be8a资料持续更新关注获取最新分享。