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

AC自动机的核心组成

• Trie 树：将所有模式串构建成一棵前缀树，每个节点代表一个字符。
• 失败指针（fail）：类似 KMP 的 next 数组，当当前路径匹配失败时，跳转到最长公共后缀对应的节点继续匹配。
• 输出函数：记录以当前节点结尾的模式串（可能有多个）。

C++ 实现步骤详解

下面我们用 C++ 一步步实现 AC 自动机。即使你是编程小白，也能跟着理解。

1. 定义 Trie 节点

struct Node {    unordered_map<char, Node*> children; // 子节点映射    Node* fail = nullptr;                // 失败指针    vector<string> output;              // 以该节点结尾的模式串        Node() {}};

2. 构建 Trie 树

将所有模式串插入到 Trie 中：

void insertPattern(Node* root, const string& pattern) {    Node* curr = root;    for (char c : pattern) {        if (curr->children.find(c) == curr->children.end()) {            curr->children[c] = new Node();        }        curr = curr->children[c];    }    curr->output.push_back(pattern); // 记录完整模式串}

3. 构建失败指针（BFS）

使用广度优先搜索（BFS）来设置每个节点的 fail 指针：

void buildFailureLinks(Node* root) {    queue<Node*> q;        // 初始化：根的所有子节点的 fail 指向 root    for (auto& kv : root->children) {        kv.second->fail = root;        q.push(kv.second);    }        while (!q.empty()) {        Node* curr = q.front();        q.pop();                for (auto& kv : curr->children) {            char c = kv.first;            Node* child = kv.second;                        // 找到 curr 的 fail 链中第一个有字符 c 子节点的节点            Node* f = curr->fail;            while (f != root && f->children.find(c) == f->children.end()) {                f = f->fail;            }                        if (f->children.find(c) != f->children.end()) {                child->fail = f->children[c];            } else {                child->fail = root;            }                        // 合并输出：如果 fail 节点有输出，也加入当前节点            if (!child->fail->output.empty()) {                child->output.insert(child->output.end(),                                      child->fail->output.begin(),                                      child->fail->output.end());            }                        q.push(child);        }    }}

4. 匹配文本

遍历文本，利用自动机进行匹配：

vector<pair<int, string>> search(const string& text, Node* root) {    vector<pair<int, string>> matches;    Node* curr = root;        for (int i = 0; i < text.size(); ++i) {        char c = text[i];                // 若当前节点没有 c 的子节点，则沿 fail 链回退        while (curr != root && curr->children.find(c) == curr->children.end()) {            curr = curr->fail;        }                if (curr->children.find(c) != curr->children.end()) {            curr = curr->children[c];        }                // 检查当前节点及其 fail 链上的所有输出        for (const string& pattern : curr->output) {            matches.push_back({i - (int)pattern.size() + 1, pattern});        }    }        return matches;}

完整使用示例

#include <iostream>#include <vector>#include <queue>#include <unordered_map>#include <string>using namespace std;// 上面定义的 Node、insertPattern、buildFailureLinks、search 函数int main() {    vector<string> patterns = {"he", "she", "his", "hers"};    string text = "ushers";        Node* root = new Node();        // 插入所有模式串    for (const string& p : patterns) {        insertPattern(root, p);    }        // 构建失败指针    buildFailureLinks(root);        // 搜索文本    auto results = search(text, root);        for (auto& match : results) {        cout << "Found \"" << match.second              << "\" at position " << match.first << endl;    }        return 0;}

总结

通过本文，你已经掌握了 AC自动机 的基本原理和 C++字符串匹配 的完整实现。这种 多模式匹配算法 在实际工程中应用广泛，性能远超逐个使用 KMP 或暴力匹配。建议你动手敲一遍代码，加深理解，并尝试优化（例如使用数组代替 map 提高速度）。

记住，掌握 AC自动机实现 不仅能提升你的算法能力，还能为处理大规模文本匹配任务打下坚实基础！