AC自动机详解（C++实现多模式字符串匹配的高效算法）

一、什么是AC自动机？

AC自动机结合了字典树（Trie）和KMP算法的思想：

• Trie树：用于存储所有待匹配的模式串（关键词）。
• 失败指针（fail pointer）：当匹配失败时，跳转到最长公共后缀对应的节点，避免回溯，提高效率。

通过预处理构建自动机后，可以在 O(n + m + z) 的时间复杂度内完成匹配，其中 n 是文本长度，m 是所有模式串总长度，z 是匹配结果数量。

二、AC自动机的核心结构

我们需要定义一个 Trie 节点，包含以下信息：

• 子节点指针（通常用数组或 map）
• 失败指针（fail）
• 是否为单词结尾（isEnd）
• 该节点代表的单词数量（可选，用于统计）

三、C++实现步骤

1. 定义 Trie 节点

struct Node {    Node* children[26];  // 假设只处理小写字母    Node* fail;    bool isEnd;    int count;  // 记录以该节点结尾的模式串数量    Node() {        for (int i = 0; i < 26; ++i) children[i] = nullptr;        fail = nullptr;        isEnd = false;        count = 0;    }};

2. 插入模式串到 Trie 树

void insert(Node* root, const string& word) {    Node* cur = root;    for (char c : word) {        int idx = c - 'a';        if (!cur->children[idx]) {            cur->children[idx] = new Node();        }        cur = cur->children[idx];    }    cur->isEnd = true;    cur->count++;  // 同一个词可能多次插入}

3. 构建失败指针（BFS）

使用广度优先搜索（BFS）构建 fail 指针：

void buildFailPointer(Node* root) {    queue q;    // 初始化：根节点的子节点 fail 指向 root    for (int i = 0; i < 26; ++i) {        if (root->children[i]) {            root->children[i]->fail = root;            q.push(root->children[i]);        } else {            root->children[i] = root;  // 优化：空指针指向 root        }    }    while (!q.empty()) {        Node* current = q.front();        q.pop();        for (int i = 0; i < 26; ++i) {            if (current->children[i]) {                Node* child = current->children[i];                child->fail = current->fail->children[i];                // 如果 fail 节点是结束节点，也应标记                if (child->fail->isEnd) {                    child->isEnd = true;                    child->count += child->fail->count;                }                q.push(child);            } else {                // 优化：直接指向 fail 节点的对应子节点                current->children[i] = current->fail->children[i];            }        }    }}

4. 匹配文本

int search(Node* root, const string& text) {    Node* cur = root;    int totalMatches = 0;    for (char c : text) {        int idx = c - 'a';        cur = cur->children[idx];  // 利用优化后的 Trie        // 沿着 fail 链统计所有匹配        Node* temp = cur;        while (temp != root && temp->count > 0) {            totalMatches += temp->count;            temp->count = 0;  // 避免重复计数（可选）            temp = temp->fail;        }    }    return totalMatches;}

四、完整示例代码

#include #include #include #include using namespace std;struct Node {    Node* children[26];    Node* fail;    bool isEnd;    int count;    Node() {        for (int i = 0; i < 26; ++i) children[i] = nullptr;        fail = nullptr;        isEnd = false;        count = 0;    }};void insert(Node* root, const string& word) {    Node* cur = root;    for (char c : word) {        int idx = c - 'a';        if (!cur->children[idx]) {            cur->children[idx] = new Node();        }        cur = cur->children[idx];    }    cur->isEnd = true;    cur->count++;}void buildFailPointer(Node* root) {    queue q;    for (int i = 0; i < 26; ++i) {        if (root->children[i]) {            root->children[i]->fail = root;            q.push(root->children[i]);        } else {            root->children[i] = root;        }    }    while (!q.empty()) {        Node* current = q.front();        q.pop();        for (int i = 0; i < 26; ++i) {            if (current->children[i] && current->children[i] != root) {                Node* child = current->children[i];                child->fail = current->fail->children[i];                if (child->fail->isEnd) {                    child->isEnd = true;                    child->count += child->fail->count;                }                q.push(child);            } else {                current->children[i] = current->fail->children[i];            }        }    }}int search(Node* root, const string& text) {    Node* cur = root;    int total = 0;    for (char c : text) {        int idx = c - 'a';        cur = cur->children[idx];        Node* temp = cur;        while (temp != root && temp->count > 0) {            total += temp->count;            temp->count = 0; // 防止重复匹配            temp = temp->fail;        }    }    return total;}int main() {    Node* root = new Node();    // 插入多个模式串    vector patterns = {"he", "she", "his", "hers"};    for (const string& p : patterns) {        insert(root, p);    }    // 构建失败指针    buildFailPointer(root);    // 在文本中搜索    string text = "ahishers";    int matches = search(root, text);    cout << "Total matches: " << matches << endl; // 输出：3    return 0;}

五、总结

通过本教程，你已经掌握了如何用 C++语言 实现 AC自动机。这种多模式匹配算法在实际工程中非常实用，尤其适合需要同时匹配大量关键词的场景。记住三个关键步骤：建 Trie、连 fail、跑匹配。

如果你正在开发敏感词过滤系统、日志分析工具或生物信息学软件，AC自动机实现将是你不可或缺的利器！

提示：实际项目中建议使用智能指针管理内存，或封装成类以提高代码可维护性。