C++怎么实现一个AC自动机_C++高效解决多模式串匹配问题的算法

AC自动机通过构建Trie树、失败指针和执行匹配实现高效多模式串查找，时间复杂度为O(n + m + z)，适用于大规模关键词匹配。

AC自动机（Aho-Corasick Automaton）是一种用于高效解决多模式串匹配的经典算法。当需要在一个主串中查找多个模式串是否出现时，使用AC自动机比逐个进行KMP或暴力匹配要高效得多。C++实现AC自动机主要包含三个步骤：构建Trie树、构建失败指针（fail指针）、执行匹配。

构建Trie树

将所有模式串插入到Trie树中，每个节点代表一个字符，路径从根到叶表示一个完整的模式串。同时在每个节点记录是否为某个模式串的结尾，并保存对应的模式串编号或出现次数。

- 每个节点用数组或map存储子节点指针 - 设置一个标记变量表示该节点是否为某个模式串的结束 - 可额外记录模式串索引或数量

示例结构：

struct Node {
    int next[26]; // 假设只有小写字母
    bool isEnd;
    int id;       // 模式串编号
    Node() {
        fill(next, next + 26, -1);
        isEnd = false;
        id = -1;
    }
};
vector trie(1); // 初始化根节点

构建失败指针（Fail指针）

失败指针的作用类似于KMP中的next数组，用于在匹配失败时跳转到最长公共前后缀的位置。通过BFS遍历Trie树来构建fail指针。

- 根节点的所有直接子节点的fail指向根 - 对于当前节点u的子节点v，查找trie[u].fail对应节点是否有相同字符的子节点 - 如果有，则v的fail指向那个子节点；否则继续沿fail链向上找 - 若最终没找到，指向根节点

BFS过程伪代码逻辑：

queue q;
for (int i = 0; i < 26; ++i) {
    if (trie[0].next[i] != -1) {
        int child = trie[0].next[i];
        fail[child] = 0;
        q.push(child);
    }
}
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int i = 0; i < 26; ++i) {
        int &v = trie[u].next[i];
        int f = fail[u];
        if (v != -1) {
            while (f != -1 && trie[f].next[i] == -1) f = fail[f];
            fail[v] = (f == -1) ? 0 : trie[f].next[i];
            q.push(v);
        }
    }
}

执行多模式匹配

从主串第一个字符开始，在Trie树上逐字符转移状态。如果当前节点没有对应子节点，则通过fail指针回溯，直到可以转移或回到根节点。

- 遍历主串每个字符c - 当前状态为cur，尝试转移到trie[cur].next[c-'a'] - 若无法转移，通过fail链寻找可转移位置 - 每到达一个节点，沿fail链回溯所有可能的模式串结尾并记录结果

关键匹配逻辑：

int cur = 0; for (char c : text) { int idx = c - 'a'; while (cur != -1 && trie[cur].next[idx] == -1) cur = fail[cur]; cur = (cur == -1) ? 0 : trie[cur].next[idx];

int temp = cur;
while (temp != 0) {
    if (trie[temp].isEnd) {
        cout << "Pattern found at position: "
             << i - pattern_len + 1 << endl;
    }
    temp = fail[temp];
}

}

优化建议：

使用静态数组代替vector以提升性能
合并重复模式串避免冗余
在构建fail指针时同时更新输出链（output link），避免每次匹配都遍历fail链

基本上就这些。AC自动机的时间复杂度为O(n + m + z)，其中n是主串长度，m是所有模式串总长度，z是匹配次数，非常适合大规模多关键词匹配场景。

# node # ai # c++ # asic # 指针 # map # 算法 # 关键词 # 遍历 # 多模 # 是一种 # 第一个 # 多个 # 适用于 # 得多 # 现时 # 类似于

返回目录在线咨询

上一篇：Vue.js实战之Vuex的入门教程
下一篇：如何选择适合的域名和空间来搭建网站？

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

全网整合营销服务商

C++怎么实现一个AC自动机_C++高效解决多模式串匹配问题的算法

构建Trie树

构建失败指针（Fail指针）

执行多模式匹配

您的项目需求