信奥新赛季进入冲刺阶段，字符串算法是各大省级、校级 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

二、核心考点拆解

回文自动机的精髓，是建两棵"树"，让每个节点代表一个本质不同的回文子串。

1. 双根结构：维护两个虚根——节点0是偶数长度回文的根（len=0），节点1是奇数长度回文的根（len=-1）。真实回文节点从2号开始，因此本质不同回文个数 =节点总数 − 2。
2. 节点含义：每个节点u存len[u]（该回文长度）、fail[u]（最长"真回文后缀"指针，类似后缀自动机的后缀链接）、ch[u][c]（在左右各加字符c后跳转到的节点）、cnt[u]（出现次数）。
3. get_fail跳链：给定当前位置i和节点x，沿fail向上跳，直到S[i]与S[i − len[x] − 1]相等——也就是说，x代表的回文串左右各加一个S[i]后仍是回文。
4. extend增量插入：逐字符插入。若ch[x][S[i]]已存在，说明该回文早已建好，仅把出现次数+1；否则新建节点，len = len[x] + 2，并算出它的fail。
5. fail的计算：新节点的fail指向"去掉首尾字符后最长的回文后缀"，通过get_fail(fail[x], i)找到后再取其字符c的转移；单字符回文（len=1）的fail固定指向偶根0（空串）。
6. 出现次数上推：插入时只在"以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; vector<int> len, fail, cnt; vector<array<int, 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, array<int, 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(array<int, 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)。

五、六个高频易错点

1. 双根初始化：len必须是[0, -1]，fail是[1, 0]，tot从2起步。fail[0]=1保证偶根跳空后落到奇根，fail[1]=0是奇根的兜底。
2. get_fail的越界判断：i − len[x] − 1 < 0必须先判，否则访问s[-1]越界。这是回文自动机最常见的段错误来源。
3. 单字符回文的特殊fail：len=1的新节点fail要显式指向 0（偶根），不能走通用公式，否则会得到指向自身的错误后缀链接。
4. fail拓扑顺序：出现次数上推必须按节点编号从大到小遍历（fail[u] < u恒成立），从小到大会漏算。
5. 本质不同回文个数 =tot − 2：两个虚根不算真实回文，千万别漏减 2，也不要把空串（偶根）算进去。
6. 字符集与数组大小：用固定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 内打开，也可复制下方明文链接：

1. 全国青少年信息素养大赛复赛集训题目Python&C++.docx
   https://pan.quark.cn/s/93995d3cb150
2. 2024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdf
   https://pan.quark.cn/s/da97b5dbf75d
3. Python背记手册.pdf
   https://pan.quark.cn/s/7568ae9ca92b
4. Python课程
   https://pan.quark.cn/s/a94bf02d00c6
5. 2024信息素养大赛图形化复赛集训题答案3-9
   https://pan.quark.cn/s/6ccab7ec3cbc
6. 2025年03月份电子学会考级真题
   https://pan.quark.cn/s/4403c4228912
7. 2025全国青少年信息素养大赛赛项说明
   https://pan.quark.cn/s/d9d0df4a9f29
8. 青少儿信息素养大赛编程资料
   https://pan.quark.cn/s/4ab6bd83be8a

资料持续更新，关注获取最新分享。