本文详解 C++ 回文自动机（PAM），一种用于处理字符串回文子串的高效数据结构。文章涵盖核心背景、节点设计、构建流程及五大应用场景，包括统计本质不同回文数、总出现次数、最长回文子串等。提供完整代码实现与类封装示例，对比 Manacher 等算法，并给出优化技巧与常见错误排查，适合算法竞赛及工程实践参考。
回文自动机（Palindrome Automaton, PAM，也叫回文树）是专门处理字符串回文子串问题的高效数据结构，由 Mikhail Rubinchik 在 2015 年提出。它能在 O(n) 时间复杂度内构建，支持统计回文子串数量、查找最长回文子串、统计各长度回文子串出现次数等核心问题，是处理回文问题的'专属利器'。本文将从核心原理、节点设计、构建流程到实战应用，全面解析回文自动机的设计思想与 C++ 实现技巧。
传统处理回文子串的方法（如中心扩展法 O(n^2)、Manacher 算法 O(n)）存在明显局限：
回文自动机的核心价值：
回文自动机的设计基于回文的核心性质：一个长度大于 2 的回文子串，其去掉首尾字符后仍是回文子串。核心定义如下：
trans[u][c] = v 表示在节点 u 对应回文子串的首尾添加字符 c 后，得到节点 v 对应的回文子串；示例：字符串 s = "abba" 的回文自动机结构：
偶根（0，len=0，fail=-1） ├─ fail → 奇根（1，len=-1，fail=-1） ├─ trans['a'] → 节点 2（len=1，"a"，fail=1） │ └─ trans['b'] → 节点 3（len=3，"aba"，fail=2）（若有） └─ trans['b'] → 节点 4（len=1，"b"，fail=1） └─ trans['b'] → 节点 5（len=2，"bb"，fail=0） └─ trans['a'] → 节点 6（len=4，"abba"，fail=2）
回文自动机的核心是节点结构和全局状态管理，C++ 实现如下：
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
// 回文自动机节点结构
struct PAMNode {
int trans[26]; // 字符到节点的转移（仅处理小写字母，可扩展）
int fail; // 失败指针
int len; // 对应回文子串的长度
int cnt; // 该回文子串的出现次数（可选，统计次数用）
// 初始化节点
PAMNode() {
memset(trans, -1, sizeof(trans));
fail = -1;
len = 0;
cnt = 0;
}
};
// 回文自动机核心全局变量（封装为类更佳）
vector<PAMNode> pam; // 所有节点的集合
string s; // 输入字符串
int last; // 最后一个字符结尾的最长回文子串节点
int size; // 节点总数
初始化回文自动机的两个根节点（偶根、奇根），并设置初始状态：
// 初始化回文自动机
void init_pam() {
pam.clear();
// 创建偶根（0 号）和奇根（1 号）
pam.emplace_back(); // 0: 偶根，len=0
pam.emplace_back(); // 1: 奇根，len=-1
pam[0].fail = 1; // 偶根的失败指针指向奇根
pam[1].len = -1; // 奇根长度为 -1
last = 0; // 初始 last 指向偶根
size = 2; // 初始节点数为 2
}
给定当前节点 cur 和字符索引 i，查找能以 s[i] 为结尾的最长回文子串对应的节点（核心！）：
// 查找：从 cur 出发，找到满足 s[i - len[cur] - 1] == s[i] 的节点
int find(int cur, int i) {
// 回退：直到找到满足条件的节点，或到奇根
while (i - pam[cur].len - 1 < 0 || s[i - pam[cur].len - 1] != s[i]) {
cur = pam[cur].fail;
}
return cur;
}
回文自动机的构建是'增量式'的：遍历字符串每个字符，逐步扩展回文子串，核心步骤为「查找→创建节点→设置失败指针→更新转移→更新 last」。
// 向回文自动机中添加字符 s[i]
void add_char(int i) {
char c = s[i];
int idx = c - 'a';
// 步骤 1：查找能以 s[i] 结尾的最长回文子串的前驱节点
int cur = find(last, i);
// 步骤 2：检查转移是否存在，不存在则创建新节点
if (pam[cur].trans[idx] == -1) {
// 2.1 创建新节点
pam.emplace_back();
int new_node = size++;
pam[new_node].len = pam[cur].len + 2; // 回文子串长度 +2（首尾加字符）
// 2.2 设置新节点的失败指针
if (pam[new_node].len == 1) {
// 长度为 1 的回文子串（单个字符），失败指针指向奇根
pam[new_node].fail = 1;
} else {
// 查找失败指针的前驱节点，再取转移
int fail_cur = find(pam[cur].fail, i);
pam[new_node].fail = pam[fail_cur].trans[idx];
}
// 2.3 更新转移表
pam[cur].trans[idx] = new_node;
}
// 步骤 3：更新 last 为当前字符结尾的最长回文子串节点
last = pam[cur].trans[idx];
// 步骤 4：统计出现次数（可选，最后需反向更新）
pam[last].cnt++;
}
// 构建整个字符串的回文自动机
void build_pam(const string& input) {
s = input;
init_pam();
for (int i = 0; i < s.size(); ++i) {
add_char(i);
}
// 反向更新 cnt：统计每个回文子串的真实出现次数（失败指针的 cnt 累加到当前节点）
for (int i = size - 1; i >= 2; --i) {
if (pam[i].fail != -1) {
pam[pam[i].fail].cnt += pam[i].cnt;
}
}
}
// 打印所有本质不同的回文子串及其出现次数
void print_palindromes() {
cout << "本质不同的回文子串：" << endl;
// 跳过前两个根节点（0：偶根，1：奇根）
for (int i = 2; i < size; ++i) {
cout << "长度：" << pam[i].len << "，出现次数：" << pam[i].cnt << endl;
}
}
// 查找最长回文子串
int find_longest_palindrome() {
int max_len = 0;
for (int i = 2; i < size; ++i) {
max_len = max(max_len, pam[i].len);
}
return max_len;
}
// 统计所有回文子串的总数（包括重复）
long long count_all_palindromes() {
long long total = 0;
for (int i = 2; i < size; ++i) {
total += pam[i].cnt;
}
return total;
}
int main() {
string input = "abba";
build_pam(input);
cout << "输入字符串：" << input << endl;
cout << "最长回文子串长度：" << find_longest_palindrome() << endl; // 4
cout << "本质不同的回文子串数量：" << size - 2 << endl; // 4（a、b、bb、abba）
cout << "所有回文子串总数：" << count_all_palindromes() << endl; // 5（a:1, b:2, bb:1, abba:1 → 总计 5）
print_palindromes();
return 0;
}
输出结果：
输入字符串：abba
最长回文子串长度：4
本质不同的回文子串数量：4
所有回文子串总数：5
本质不同的回文子串：
长度：1，出现次数：1
长度：1，出现次数：2
长度：2，出现次数：1
长度：4，出现次数：1
本质不同的回文子串数量 = 回文自动机的节点数 - 2（减去两个根节点）：
int count_distinct_palindromes() {
return size - 2;
}
通过 cnt 字段累加即可（需先反向更新 cnt）：
long long count_total_palindromes() {
long long total = 0;
for (int i = 2; i < size; ++i) {
total += pam[i].cnt;
}
return total;
}
遍历所有节点，找到 len 最大的节点：
string find_longest_palindrome_str() {
int max_len = 0;
int max_node = -1;
for (int i = 2; i < size; ++i) {
if (pam[i].len > max_len) {
max_len = pam[i].len;
max_node = i;
}
}
// 反向查找最长回文子串的起始位置（可选）
if (max_len == 0) return "";
// 简化：直接遍历字符串找最长回文子串（也可通过 PAM 的节点回溯）
for (int i = 0; i <= s.size() - max_len; ++i) {
string sub = s.substr(i, max_len);
// 验证是否为回文
bool is_pali = true;
for (int j = 0; j < max_len / 2; ++j) {
if (sub[j] != sub[max_len - 1 - j]) {
is_pali = false;
break;
}
}
if (is_pali) return sub;
}
return "";
}
vector<int> count_palindrome_by_len(int max_len) {
vector<int> res(max_len + 1, 0);
for (int i = 2; i < size; ++i) {
int len = pam[i].len;
if (len <= max_len) {
res[len] += pam[i].cnt;
}
}
return res;
}
// 测试：count_palindrome_by_len(4) → [0,3,1,0,1]（长度 1：3 次，长度 2：1 次，长度 4：1 次）
bool is_palindrome(const string& input) {
build_pam(input);
int max_len = find_longest_palindrome();
return max_len == input.size();
}
trans[26] 改为 unordered_map<char, int>；reserve 节点数组空间（如 pam.reserve(n + 2)），避免频繁扩容；cnt 字段和反向更新步骤。fail 未指向奇根，或奇根的 len 未设为 -1，导致查找失败指针时死循环；i - pam[cur].len - 1 < 0，导致字符串越界访问；cnt 字段统计出现次数，结果偏小（失败指针的 cnt 未累加）；last，导致后续查找错误。| 算法/数据结构 | 时间复杂度 | 空间复杂度 | 核心优势 | 缺点 |
|---|---|---|---|---|
| 回文自动机 | O(n) | O(n) | 统计所有回文子串信息，灵活 | 实现略复杂 |
| Manacher 算法 | O(n) | O(n) | 仅找最长回文子串，实现简单 | 无法统计所有回文子串 |
| 中心扩展法 | O(n^2) | O(1) | 实现极简 | 时间复杂度高 |
| 后缀自动机 | O(n) | O(n) | 通用，支持更多字符串问题 | 针对性差，需额外处理回文 |
选择建议：
将全局变量封装为类，提升代码的可维护性和复用性：
class PalindromeAutomaton {
private:
struct Node {
int trans[26];
int fail;
int len;
int cnt;
Node() {
memset(trans, -1, sizeof(trans));
fail = -1;
len = 0;
cnt = 0;
}
};
vector<Node> nodes;
string s;
int last;
int size;
// 查找辅助函数
int find(int cur, int i) {
while (i - nodes[cur].len - 1 < 0 || s[i - nodes[cur].len - 1] != s[i]) {
cur = nodes[cur].fail;
}
return cur;
}
// 初始化
void init() {
nodes.clear();
nodes.emplace_back(); // 0: 偶根
nodes.emplace_back(); // 1: 奇根
nodes[0].fail = 1;
nodes[1].len = -1;
last = 0;
size = 2;
}
public:
PalindromeAutomaton() = default;
// 构建回文自动机
void build(const string& input) {
s = input;
init();
for (int i = 0; i < s.size(); ++i) {
add(i);
}
// 反向更新 cnt
for (int i = size - 1; i >= 2; --i) {
if (nodes[i].fail != -1) {
nodes[nodes[i].fail].cnt += nodes[i].cnt;
}
}
}
// 添加单个字符
void add(int i) {
char c = s[i];
int idx = c - 'a';
int cur = find(last, i);
if (nodes[cur].trans[idx] == -1) {
nodes.emplace_back();
int new_node = size++;
nodes[new_node].len = nodes[cur].len + 2;
if (nodes[new_node].len == 1) {
nodes[new_node].fail = 1;
} else {
int fail_cur = find(nodes[cur].fail, i);
nodes[new_node].fail = nodes[fail_cur].trans[idx];
}
nodes[cur].trans[idx] = new_node;
}
last = nodes[cur].trans[idx];
nodes[last].cnt++;
}
// 统计本质不同的回文子串数量
int count_distinct() {
return size - 2;
}
// 统计所有回文子串总数
long long count_total() {
long long total = 0;
for (int i = 2; i < size; ++i) {
total += nodes[i].cnt;
}
return total;
}
// 查找最长回文子串长度
int longest_palindrome_len() {
int max_len = 0;
for (int i = 2; i < size; ++i) {
max_len = max(max_len, nodes[i].len);
}
return max_len;
}
};
// 测试类实现
int main() {
PalindromeAutomaton pam;
pam.build("abba");
cout << "本质不同的回文子串数：" << pam.count_distinct() << endl; // 4
cout << "所有回文子串总数：" << pam.count_total() << endl; // 5
cout << "最长回文子串长度：" << pam.longest_palindrome_len() << endl; // 4
return 0;
}
回文自动机是处理回文子串问题的'专属神器'，核心要点可总结为：
掌握回文自动机的关键：
find 函数的逻辑（核心查找步骤，避免越界）；回文自动机是 C++ 算法竞赛中处理回文问题的必考知识点，其设计思想（增量构建、失败指针）与 AC 自动机、后缀自动机一脉相承，理解它能帮助你更系统地掌握字符串数据结构体系。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online