C++算法
C++ AC 自动机：原理、实现与应用
AC 自动机是一种结合字典树和 KMP 算法的高效多模式匹配算法，用于在文本中同时匹配多个关键词。其核心在于利用失败指针实现失配后的快速回退，将匹配时间复杂度降为线性。详细阐述了 AC 自动机的数据结构设计、构建流程（Trie 插入、BFS 建 Fail 指针、文本匹配），提供了完整的 C++ 实现代码，并探讨了字符集扩展、出现次数统计及路径压缩等优化方案，最后总结了敏感词过滤、日志分析等典型应用场景。
AC 自动机是一种结合字典树和 KMP 算法的高效多模式匹配算法，用于在文本中同时匹配多个关键词。其核心在于利用失败指针实现失配后的快速回退，将匹配时间复杂度降为线性。详细阐述了 AC 自动机的数据结构设计、构建流程（Trie 插入、BFS 建 Fail 指针、文本匹配），提供了完整的 C++ 实现代码，并探讨了字符集扩展、出现次数统计及路径压缩等优化方案，最后总结了敏感词过滤、日志分析等典型应用场景。
AC 自动机（Aho-Corasick Automaton）是结合字典树（Trie）和KMP 算法思想的高效多模式匹配算法，核心解决'在一段文本中同时匹配多个模式串（关键词）'的问题。其优势在于：预处理模式串的时间复杂度为 O(∑len)（∑len 为所有模式串总长度），文本匹配的时间复杂度为 O(n)（n 为文本长度），远优于暴力匹配（O(n · ∑len)）。本文将从核心原理、结构设计、构建流程到实战应用，全面解析 AC 自动机的设计思想与 C++ 实现技巧。
在文本处理场景（如敏感词过滤、日志关键词提取）中，需同时匹配数十/数百个模式串，传统方法存在明显缺陷：
AC 自动机的核心改进：
AC 自动机基于 Trie 扩展，包含三个核心部分：
app，输出链表包含 app；若同时对应 p，则包含 p）。示例：模式串为 he、she、his、hers 的 AC 自动机结构（简化）：
根节点（fail=null） ├─ h (fail=根)
│ ├─ e (fail=根->e，输出：he)
│ │ └─ r (fail=根)
│ │ └─ s (fail=根->s，输出：hers)
│ └─ i (fail=根)
│ └─ s (fail=根->s，输出：his)
├─ s (fail=根)
│ └─ h (fail=根->h)
│ └─ e (fail=根->h->e，输出：she)
└─ e (fail=根)
AC 自动机的节点在 Trie 节点基础上，新增 失败指针 和 输出标记（记录是否为模式串结尾，或存储模式串列表）：
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
struct ACNode {
// 子节点：26 个小写字母，-1 表示无节点（用索引替代指针，简化内存管理）
int children[26];
// 失败指针：指向其他节点的索引（根节点 fail=-1）
int fail;
// 结束标记：存储以当前节点为结尾的模式串长度（>0 表示是模式串结尾，值为长度）
// 也可改为 vector<string> 存储具体模式串，按需选择
int len;
// 初始化节点
ACNode() {
memset(children, -1, sizeof(children));
fail = -1;
len = 0;
}
};
len > 0，表示当前节点是一个模式串的结尾，len 为该模式串的长度（便于匹配时快速提取关键词）。AC 自动机包含三个核心部分：节点数组（存储所有节点）、根节点索引、队列（用于 BFS 构建失败指针）：
class ACAutomaton {
private:
vector<ACNode> nodes; // 节点数组（动态扩展）
int root; // 根节点索引
// 新建节点，返回索引
int newNode() {
nodes.emplace_back();
return nodes.size() - 1;
}
public:
// 构造函数：初始化根节点
ACAutomaton() { root = newNode(); }
// 核心操作：插入模式串、构建失败指针、文本匹配
void insert(const string& pattern);
void buildFail();
vector<pair<int, int>> match(const string& text); // 返回 <起始位置，模式串长度>
};
AC 自动机的构建分为两步：插入所有模式串构建 Trie → BFS 遍历构建失败指针。
与普通 Trie 的插入逻辑一致，逐个字符插入，最后标记模式串结尾：
void ACAutomaton::insert(const string& pattern) {
int cur = root;
for (char c : pattern) {
int idx = c - 'a'; // 仅处理小写字母，可扩展为其他字符集
// 子节点不存在则新建
if (nodes[cur].children[idx] == -1) {
nodes[cur].children[idx] = newNode();
}
// 移动到子节点
cur = nodes[cur].children[idx];
}
// 标记当前节点为模式串结尾，记录长度
nodes[cur].len = pattern.size();
}
示例：插入 he → 根→h→e，e 节点的 len=2；插入 she → 根→s→h→e，e 节点的 len=2。
失败指针的构建遵循以下规则：
p，p 通过字符 c 指向 u；找到 p 的失败指针 fail_p，若 fail_p 有字符 c 的子节点 v，则 u 的失败指针指向 v；否则继续找 fail_p 的失败指针，直到根节点。u 的失败指针指向 v，则 v 的输出（模式串）也属于 u 的匹配结果（需在匹配时回溯）。void ACAutomaton::buildFail() {
queue<int> q;
// 第一步：初始化根节点的所有子节点
for (int i = 0; i < 26; ++i) {
int child = nodes[root].children[i];
if (child != -1) {
nodes[child].fail = root; // 子节点失败指针指向根
q.push(child); // 加入 BFS 队列
}
}
// 第二步：BFS 遍历所有节点，构建失败指针
while (!q.empty()) {
int p = q.front(); // 当前节点（父节点）
q.pop();
// 遍历当前节点的所有子节点
for (int i = 0; i < 26; ++i) {
int u = nodes[p].children[i]; // 子节点 u（字符 i 对应的节点）
if (u == -1) continue;
// 找 p 的失败指针 fail_p
int fail_p = nodes[p].fail;
// 回溯：直到找到有字符 i 的子节点，或到根节点
while (fail_p != -1 && nodes[fail_p].children[i] == -1) {
fail_p = nodes[fail_p].fail;
}
// 设置 u 的失败指针
if (fail_p == -1) {
nodes[u].fail = root; // 回溯到根仍未找到，指向根
} else {
nodes[u].fail = nodes[fail_p].children[i];
}
// 将 u 加入队列，处理其子节点
q.push(u);
}
}
}
关键逻辑：失败指针的构建是'层序遍历'（BFS），确保父节点的失败指针先于子节点构建完成。
匹配逻辑：从根节点开始遍历文本，利用失败指针快速回退，同时收集所有匹配的模式串：
vector<pair<int, int>> ACAutomaton::match(const string& text) {
vector<pair<int, int>> res; // 存储 <匹配起始位置，模式串长度>
int cur = root;
for (int i = 0; i < text.size(); ++i) {
int idx = text[i] - 'a';
// 失配：通过失败指针回退，直到根节点或找到匹配的子节点
while (cur != root && nodes[cur].children[idx] == -1) {
cur = nodes[cur].fail;
}
// 匹配：移动到子节点
if (nodes[cur].children[idx] != -1) {
cur = nodes[cur].children[idx];
}
// 收集所有匹配的模式串（回溯失败指针，获取所有后缀匹配）
int temp = cur;
while (temp != root) {
// 若当前节点是模式串结尾，记录匹配结果
if (nodes[temp].len > 0) {
int start = i - nodes[temp].len + 1; // 计算起始位置
res.emplace_back(start, nodes[temp].len);
}
// 回溯失败指针，检查是否有更长的后缀匹配
temp = nodes[temp].fail;
}
}
return res;
}
示例：文本 ushers，匹配模式串 he、she、his、hers：
s（i=0）→ 无匹配；h（i=1）→ 无匹配；e（i=2）→ 匹配 he（起始 0，长度 2）、she（起始 1，长度 2）；r（i=3）→ 无匹配；s（i=4）→ 匹配 hers（起始 1，长度 4）；s（i=5）→ 无匹配。#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <cstring>
#include <utility>
using namespace std;
struct ACNode {
int children[26];
int fail;
int len; // 模式串长度，0 表示非结尾
ACNode() {
memset(children, -1, sizeof(children));
fail = -1;
len = 0;
}
};
class ACAutomaton {
private:
vector<ACNode> nodes;
int root;
int newNode() {
nodes.emplace_back();
return nodes.size() - 1;
}
public:
ACAutomaton() { root = newNode(); }
// 插入模式串（仅小写字母）
void insert(const string& pattern) {
int cur = root;
for (char c : pattern) {
int idx = c - 'a';
if (nodes[cur].children[idx] == -1) {
nodes[cur].children[idx] = newNode();
}
cur = nodes[cur].children[idx];
}
nodes[cur].len = pattern.size();
}
// 构建失败指针（BFS）
void buildFail() {
queue<int> q;
// 初始化根节点的子节点
for (int i = 0; i < 26; ++i) {
int child = nodes[root].children[i];
if (child != -1) {
nodes[child].fail = root;
q.push(child);
}
}
// BFS 遍历
while (!q.empty()) {
int p = q.front();
q.pop();
for (int i = 0; i < 26; ++i) {
int u = nodes[p].children[i];
if (u == -1) continue;
// 找失败指针
int fail_p = nodes[p].fail;
while (fail_p != -1 && nodes[fail_p].children[i] == -1) {
fail_p = nodes[fail_p].fail;
}
nodes[u].fail = (fail_p == -1) ? root : nodes[fail_p].children[i];
q.push(u);
}
}
}
// 匹配文本，返回所有匹配的 <起始位置，模式串长度>
vector<pair<int, int>> match(const string& text) {
vector<pair<int, int>> res;
int cur = root;
for (int i = 0; i < text.size(); ++i) {
// 仅处理小写字母，非小写字母重置为根节点
if (!islower(text[i])) {
cur = root;
continue;
}
int idx = text[i] - 'a';
// 失配回退
while (cur != root && nodes[cur].children[idx] == -1) {
cur = nodes[cur].fail;
}
// 匹配移动
if (nodes[cur].children[idx] != -1) {
cur = nodes[cur].children[idx];
}
// 收集所有匹配结果
int temp = cur;
while (temp != root) {
if (nodes[temp].len > 0) {
int start = i - nodes[temp].len + 1;
res.emplace_back(start, nodes[temp].len);
}
temp = nodes[temp].fail;
}
}
return res;
}
};
// 测试代码
int main() {
// 1. 初始化 AC 自动机，插入模式串
ACAutomaton ac;
vector<string> patterns = {"he", "she", "his", "hers"};
for (const string& p : patterns) {
ac.insert(p);
}
// 2. 构建失败指针
ac.buildFail();
// 3. 匹配文本
string text = "ushers";
vector<pair<int, int>> res = ac.match(text);
// 4. 输出匹配结果
cout << "文本：" << text << endl;
cout << "匹配结果（起始位置，长度）：" << endl;
for (auto& [start, len] : res) {
cout << "位置 " << start << ":" << text.substr(start, len) << endl;
}
return 0;
}
输出结果：
文本：ushers
匹配结果（起始位置，长度）：
位置 1:he
位置 0:she
位置 1:hers
若需处理大写字母、数字、符号等，将 children[26] 改为 unordered_map<char, int>：
struct ACNode {
unordered_map<char, int> children; // 动态字符映射
int fail;
int len;
ACNode() : fail(-1), len(0) {}
};
// 插入逻辑调整
void insert(const string& pattern) {
int cur = root;
for (char c : pattern) {
if (!nodes[cur].children.count(c)) {
nodes[cur].children[c] = newNode();
}
cur = nodes[cur].children[c];
}
nodes[cur].len = pattern.size();
}
// 构建失败指针调整
void buildFail() {
queue<int> q;
// 初始化根节点子节点
for (auto& [c, child] : nodes[root].children) {
nodes[child].fail = root;
q.push(child);
}
while (!q.empty()) {
int p = q.front();
q.pop();
for (auto& [c, u] : nodes[p].children) {
int fail_p = nodes[p].fail;
// 回溯找 c 对应的子节点
while (fail_p != -1 && !nodes[fail_p].children.count(c)) {
fail_p = nodes[fail_p].fail;
}
nodes[u].fail = (fail_p == -1) ? root : nodes[fail_p].children[c];
q.push(u);
}
}
}
在节点中新增 count 属性，记录模式串出现次数：
struct ACNode {
int children[26];
int fail;
int len;
int count; // 新增：模式串出现次数
ACNode() {
memset(children, -1, sizeof(children));
fail = -1;
len = 0;
count = 0;
}
};
// 匹配时统计次数
vector<pair<string, int>> countPattern(const string& text, const vector<string>& patterns) {
// 先构建模式串到长度的映射
unordered_map<int, vector<string>> len2pattern;
for (const string& p : patterns) {
len2pattern[p.size()].push_back(p);
}
// 匹配文本
auto res = match(text);
unordered_map<string, int> cnt;
for (auto& [start, len] : res) {
string sub = text.substr(start, len);
cnt[sub]++;
}
// 整理结果
vector<pair<string, int>> ret;
for (const string& p : patterns) {
ret.emplace_back(p, cnt[p]);
}
return ret;
}
匹配时需回溯失败指针收集结果，可预先将失败指针的输出合并到当前节点（路径压缩），避免多次回溯：
// 构建失败指针后，压缩路径
void compress() {
queue<int> q;
q.push(root);
while (!q.empty()) {
int u = q.front();
q.pop();
// 合并失败指针的 len（模式串长度）
if (nodes[u].fail != -1 && nodes[u].fail != root) {
// 若当前节点无模式串，继承失败指针的模式串
if (nodes[u].len == 0) {
nodes[u].len = nodes[nodes[u].fail].len;
}
}
// 遍历子节点
for (int i = 0; i < 26; ++i) {
int child = nodes[u].children[i];
if (child != -1) {
q.push(child);
}
}
}
}
将所有敏感词存入 AC 自动机，遍历文本匹配敏感词，实现高效替换/屏蔽：
string filterSensitiveWord(const string& text, const vector<string>& sensitiveWords, char replace = '*') {
ACAutomaton ac;
for (const string& word : sensitiveWords) {
ac.insert(word);
}
ac.buildFail();
auto res = ac.match(text);
string filtered = text;
// 替换所有敏感词为*
for (auto& [start, len] : res) {
fill(filtered.begin() + start, filtered.begin() + start + len, replace);
}
return filtered;
}
// 测试
int main() {
vector<string> sensitive = {"赌博", "色情", "毒品"}; // 需扩展字符集支持中文
string text = "禁止赌博和色情内容，远离毒品！";
cout << filterSensitiveWord(text, sensitive) << endl; // 输出：禁止***和***内容，远离***！
return 0;
}
从海量日志中快速提取所有预设关键词，用于日志分析、告警：
int main() {
vector<string> keywords = {"error", "warning", "timeout"};
ACAutomaton ac;
for (const string& kw : keywords) {
ac.insert(kw);
}
ac.buildFail();
// 模拟日志文本
string log = "2026-01-11 10:00:00 [error] connection timeout | 10:01:00 [warning] low memory";
auto res = ac.match(log);
cout << "日志中匹配的关键词：" << endl;
for (auto& [start, len] : res) {
cout << log.substr(start, len) << endl;
}
// 输出：error、timeout、warning
return 0;
}
解决 LeetCode 3016. 输入单词需要的最少按键次数 II、LeetCode 1032. 字符流等问题，AC 自动机是最优解。
unordered_map，或先统一转换为小写。temp = cur 回溯失败指针收集所有结果。children[26]，效率最高。unordered_map<char, int>，灵活但略慢。emplace_back。count 属性，匹配时累加。unordered_set 存储已匹配的模式串，避免重复。AC 自动机是多模式匹配的'终极方案'，核心特性可总结为：
掌握 AC 自动机的关键：
AC 自动机是 C++ 开发者处理文本匹配问题的核心算法，结合 Trie 和 KMP 的优势，在工业界和算法竞赛中均有广泛应用。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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