注：在阅读本文请，请先学习KMP和字典树。

AC自动机概述

AC自动机（Aho-Corasick Automaton）是一种多模式串匹配算法，用于高效地在文本中同时查找多个模式串的出现位置。其核心思想结合了Trie树和KMP算法的失败指针（fail pointer），通过预处理构建自动机，实现线性时间复杂度的匹配。

Trie树基础

AC自动机基于Trie树（字典树）构建。Trie树是一种多叉树结构，每个节点代表一个字符，从根到某一节点的路径构成一个字符串。例如，模式串集合{"he", "she", "his", "hers"}的Trie树如下：

        (root)
        /  |  \
       h   s   i
      / \   \   \
     e   i   h   s
    / \   \   \
   *   r   s   *
      /     \
     s       *
    /
   *

（注：*表示模式串的终止节点）

失败指针（Fail Pointer）

失败指针是AC自动机的核心优化。每个节点的失败指针指向当前节点匹配失败时应该跳转的节点，类似于KMP算法中的部分匹配表。失败指针的构建规则如下：

1. 根节点的失败指针为空。
2. 根的直接子节点的失败指针指向根。
3. 其他节点的失败指针通过BFS逐层计算：
   • 设当前节点为u，其父节点为p，字符为c。
   • 若p的失败指针指向的节点fail[p]有字符c的子节点v，则fail[u] = v。
   • 否则递归查找fail[p]的失败指针，直到根节点。

失败指针示例

以模式串{"he", "she", "his", "hers"}为例：

• 节点s的失败指针指向根。
• 节点h的失败指针指向根。
• 节点e的失败指针指向h（因为h是he的前缀）。

AC自动机构建步骤

1. 构建Trie树：插入所有模式串。
2. 计算失败指针：通过BFS遍历Trie树，为每个节点设置失败指针。
3. 优化路径压缩（可选）：将失败指针直接指向最终有效节点，减少跳转次数。

匹配过程

1. 从文本的起始位置和Trie树的根节点开始。
2. 若当前字符匹配成功，移动到子节点；否则通过失败指针跳转。
3. 若到达终止节点，记录匹配成功的模式串。

匹配示例

文本："ushers"，模式串{"he", "she", "his", "hers"}：

• 匹配到s时，从根节点移动到s。
• 匹配到h时，从s的子节点h移动到h。
• 匹配到e时，发现终止节点e，匹配到"she"和"he"。

C++实现代码

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    TrieNode* fail;
    vector<int> output; // 存储模式串的终止索引
};

class AhoCorasick {
private:
    TrieNode* root;

    void buildFailureLinks() {
        queue<TrieNode*> q;
        root->fail = root;
        for (auto& [ch, child] : root->children) {
            child->fail = root;
            q.push(child);
        }

        while (!q.empty()) {
            TrieNode* u = q.front();
            q.pop();
            for (auto& [ch, v] : u->children) {
                TrieNode* f = u->fail;
                while (f != root && f->children.find(ch) == f->children.end()) {
                    f = f->fail;
                }
                if (f->children.find(ch) != f->children.end()) {
                    v->fail = f->children[ch];
                } else {
                    v->fail = root;
                }
                v->output.insert(v->output.end(), v->fail->output.begin(), v->fail->output.end());
                q.push(v);
            }
        }
    }

public:
    AhoCorasick() : root(new TrieNode()) {}

    void insert(const string& word, int patternIndex) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->output.push_back(patternIndex);
    }

    void build() {
        buildFailureLinks();
    }

    vector<vector<int>> search(const string& text, int numPatterns) {
        vector<vector<int>> occurrences(numPatterns);
        TrieNode* node = root;
        for (int i = 0; i < text.size(); ++i) {
            char ch = text[i];
            while (node != root && node->children.find(ch) == node->children.end()) {
                node = node->fail;
            }
            if (node->children.find(ch) != node->children.end()) {
                node = node->children[ch];
            }
            for (int patternIdx : node->output) {
                occurrences[patternIdx].push_back(i);
            }
        }
        return occurrences;
    }
};

int main() {
    vector<string> patterns = {"he", "she", "his", "hers"};
    AhoCorasick ac;
    for (int i = 0; i < patterns.size(); ++i) {
        ac.insert(patterns[i], i);
    }
    ac.build();

    string text = "ushers";
    auto result = ac.search(text, patterns.size());
    for (int i = 0; i < patterns.size(); ++i) {
        cout << patterns[i] << ": ";
        for (int pos : result[i]) {
            cout << pos - patterns[i].length() + 1 << " ";
        }
        cout << endl;
    }
    return 0;
}

时间复杂度分析

• 构建阶段：
  • Trie树插入：O(L)，L为所有模式串总长度。
  • 失败指针计算：O(L × |Σ|)，Σ为字符集大小。
• 匹配阶段：O(n + z)，n为文本长度，z为匹配次数。

应用场景

1. 敏感词过滤：快速检测文本中的多个敏感词。
2. 生物信息学：DNA序列的多模式匹配。
3. 网络入侵检测：匹配恶意流量特征。

优化技巧

1. 双数组Trie：压缩存储空间，提高缓存命中率。
2. 路径压缩：合并失败指针的连续跳转，减少递归查询。

图示说明

（以下为示意图描述，实际实现需结合图形工具生成）

1. Trie树结构图：展示节点与字符的层级关系。
2. 失败指针图：用虚线箭头表示失败指针的跳转路径。