C++ AC 自动机：原理、实现与应用

2.1 节点（ACNode）的定义

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 标记：若 len > 0，表示当前节点是一个模式串的结尾，len 为该模式串的长度（便于匹配时快速提取关键词）。

2.2 AC 自动机的整体结构

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 自动机的核心构建流程

AC 自动机的构建分为两步：插入所有模式串构建 Trie → BFS 遍历构建失败指针。

3.1 步骤 1：插入模式串（构建 Trie）

与普通 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。

3.2 步骤 2：BFS 构建失败指针（核心！）

失败指针的构建遵循以下规则：

1. 根节点的子节点：失败指针指向根节点。
2. 普通节点 u：设其父节点为 p，p 通过字符 c 指向 u；找到 p 的失败指针 fail_p，若 fail_p 有字符 c 的子节点 v，则 u 的失败指针指向 v；否则继续找 fail_p 的失败指针，直到根节点。
3. 失败指针的继承性：若节点 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），确保父节点的失败指针先于子节点构建完成。

3.3 步骤 3：文本匹配（核心应用）

匹配逻辑：从根节点开始遍历文本，利用失败指针快速回退，同时收集所有匹配的模式串：

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

五、AC 自动机的扩展与优化

5.1 扩展 1：支持任意字符集（替代固定 26 数组）

若需处理大写字母、数字、符号等，将 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);
        }
    }
}

5.2 扩展 2：统计模式串出现次数

在节点中新增 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;
}

5.3 优化：路径压缩（Fail 树优化）

匹配时需回溯失败指针收集结果，可预先将失败指针的输出合并到当前节点（路径压缩），避免多次回溯：

// 构建失败指针后，压缩路径
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 自动机的典型应用场景

6.1 敏感词过滤

将所有敏感词存入 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;
}

6.2 日志关键词提取

从海量日志中快速提取所有预设关键词，用于日志分析、告警：

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;
}

6.3 多模式串匹配（算法竞赛）

解决 LeetCode 3016. 输入单词需要的最少按键次数 II、LeetCode 1032. 字符流等问题，AC 自动机是最优解。

七、常见错误与最佳实践

7.1 常见错误

1. 字符集处理不当：仅支持小写字母，处理大写/符号时直接崩溃 → 解决方案：扩展字符集为 unordered_map，或先统一转换为小写。
2. 失败指针构建遗漏：未 BFS 遍历所有节点，导致部分节点失败指针未初始化 → 解决方案：确保 BFS 包含所有非根节点。
3. 匹配时未回溯失败指针：仅检查当前节点，遗漏后缀匹配的模式串 → 解决方案：匹配时通过 temp = cur 回溯失败指针收集所有结果。
4. 内存溢出：模式串过多时节点数组过大 → 解决方案：限制节点数量，或使用内存池复用节点。

7.2 最佳实践

1. 字符集选择：
   • 固定小字符集（如小写字母）：用数组 children[26]，效率最高。
   • 任意字符集：用 unordered_map<char, int>，灵活但略慢。
2. 性能优化：
   • 小规模场景：用索引数组存储节点，简化内存管理。
   • 大规模场景：预分配节点数组大小，避免频繁 emplace_back。
3. 功能扩展：
   • 统计次数：新增 count 属性，匹配时累加。
   • 去重匹配：用 unordered_set 存储已匹配的模式串，避免重复。

八、总结

AC 自动机是多模式匹配的'终极方案'，核心特性可总结为：

1. 结构核心：Trie + 失败指针（借鉴 KMP 的部分匹配表），实现失配后快速回退。
2. 时间复杂度：预处理 O(∑len)，匹配 O(n)，与模式串数量无关。
3. 应用场景：敏感词过滤、日志分析、多模式串匹配等，是处理海量文本关键词的首选算法。

掌握 AC 自动机的关键：

• 理解失败指针的构建逻辑（BFS + 回溯），这是 AC 自动机的灵魂。
• 区分'前缀匹配'和'后缀匹配'，匹配时需回溯失败指针收集所有结果。
• 根据字符集选择合适的子节点存储方式，平衡效率与灵活性。

AC 自动机是 C++ 开发者处理文本匹配问题的核心算法，结合 Trie 和 KMP 的优势，在工业界和算法竞赛中均有广泛应用。