C++ 回文自动机(PAM):原理、实现与应用
回文自动机(Palindrome Automaton, PAM,也叫回文树)是专门处理字符串回文子串问题的高效数据结构,由 Mikhail Rubinchik 在 2015 年提出。它能在 O(n) 时间复杂度内构建,支持统计回文子串数量、查找最长回文子串、统计各长度回文子串出现次数等核心问题,是处理回文问题的'专属利器'。本文将从核心原理、节点设计、构建流程到实战应用,全面解析回文自动机的设计思想与 C++ 实现技巧。
本文详解 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