C++怎么实现一个AC自动机算法_C++多模式字符串匹配与Trie图-C++-PHP中文网

C++怎么实现一个AC自动机算法_C++多模式字符串匹配与Trie图

穿越時空

发布： 2025-11-23 08:32:02

原创

702人浏览过

AC自动机通过构建Trie树并引入失败指针实现多模式匹配，利用BFS构造fail指针以避免回溯，从而在O(n + m + k)时间内完成文本扫描，适用于敏感词过滤等场景。

c++怎么实现一个ac自动机算法_c++多模式字符串匹配与trie图

AC自动机（Aho-Corasick算法）是一种高效的多模式字符串匹配算法，适合在一段文本中同时查找多个关键词。它基于Trie树结构，并引入类似KMP算法的失败指针（fail pointer），实现状态间的快速跳转，从而达到线性时间复杂度的匹配效率。

构建Trie树

将所有模式串插入到Trie树中，每个节点代表一个字符，路径从根到叶构成一个完整的模式串。插入时记录每个单词的结束位置，用于匹配输出。

定义Trie节点：包含子节点指针数组、是否为单词结尾、匹配的模式串索引等信息
逐个插入模式串，每一步创建必要节点
标记最后一个节点为终止节点，并保存对应模式串的编号或内容

示例节点结构：

struct TrieNode {
    std::map<char, TrieNode*> children;
    bool isEnd;
    int patternIndex;  // 可选：记录是哪个模式串
    TrieNode* fail;
    std::vector<int> output;  // 存储在此结束的所有模式串索引
<pre class="brush:php;toolbar:false;"><pre class="brush:php;toolbar:false;">TrieNode() : isEnd(false), patternIndex(-1), fail(nullptr) {}

登录后复制

};

构造失败指针（Fail指针）

失败指针的作用是在当前匹配失败时，跳转到最长公共后缀对应的节点，避免回溯文本指针。通过广度优先遍历（BFS）构造fail指针，类似于KMP中的next数组思想。

立即学习“C++免费学习笔记（深入）”；

ExcelFormulaBot

在AI帮助下将文本指令转换为Excel函数公式

129

查看详情

根节点的fail指针指向空或自身
对每个节点的子节点，尝试继承父节点fail链上的第一个能匹配该字符的节点
如果找不到，则继续沿fail链上溯，直到根为止
使用队列进行层序遍历完成整个Trie图的构建

关键代码片段：

void buildFailPointer(TrieNode* root) {
    std::queue<TrieNode*> q;
    root->fail = nullptr;
    q.push(root);
<pre class="brush:php;toolbar:false;"><pre class="brush:php;toolbar:false;">while (!q.empty()) {
    TrieNode* curr = q.front(); q.pop();
    for (auto& [ch, child] : curr->children) {
        TrieNode* f = curr->fail;
        while (f && f->children.find(ch) == f->children.end()) {
            f = f->fail;
        }
        if (f && f->children.count(ch)) {
            child->fail = f->children[ch];
        } else {
            child->fail = root;
        }

        // 合并输出：若fail链上有结束节点，也加入output
        if (child->fail) {
            child->output.insert(child->output.end(),
                child->fail->output.begin(), child->fail->output.end());
        }

        q.push(child);
    }
}

登录后复制

}

执行多模式匹配

文本扫描过程中，从根节点开始，根据字符转移状态。若无子节点，则通过fail指针回跳，直到可以前进或回到根节点。每当进入一个节点时，检查其output列表，若有内容则表示发现匹配。

逐字符读取主串，动态更新当前状态节点
每次访问节点后，检查output是否有匹配项
可记录匹配位置和对应模式串

匹配函数示例：

std::vector<std::pair<int, int>> search(const std::string& text, TrieNode* root) {
    std::vector<std::pair<int, int>> matches; // (起始位置, 模式串索引)
    TrieNode* curr = root;
<pre class="brush:php;toolbar:false;"><pre class="brush:php;toolbar:false;">for (int i = 0; i < text.size(); ++i) {
    char ch = text[i];
    while (curr && curr->children.find(ch) == curr->children.end()) {
        curr = curr->fail;
    }
    if (curr && curr->children.count(ch)) {
        curr = curr->children[ch];
    } else {
        curr = root;
    }

    // 输出所有在此结束的模式串
    for (int idx : curr->output) {
        matches.emplace_back(i - patterns[idx].size() + 1, idx);
    }
}
return matches;

登录后复制

}

基本上就这些。AC自动机构建完成后，能在O(n + m + k)时间内完成匹配，其中n是文本长度，m是所有模式串总长，k是匹配总数。适用于敏感词过滤、关键词高亮、日志分析等场景。注意内存管理，尤其是节点释放。使用智能指针或手动析构清理Trie树更安全。

以上就是C++怎么实现一个AC自动机算法_C++多模式字符串匹配与Trie图的详细内容，更多请关注php中文网其它相关文章！