AC 自动机CSP-S

💡 核心思想

AC 自动机（Aho-Corasick）是多模式串匹配的自动化算法。它先把所有模式串建成 Trie 树，然后通过 BFS 构建失败指针（fail），使得在匹配过程中失配时可以快速跳转到下一个可能的匹配位置。一次扫描主串，即可同时匹配所有模式串，时间复杂度 O(|主串| + |模式串总长| + 匹配次数)。

🎯 直觉理解

想象你在一个巨大的文本中查找多个关键词。AC 自动机就像一个"智能扫描仪"：它先记住所有关键词的形状（Trie 树），然后一边读文本一边匹配。如果匹配失败了，它不是从头再来，而是根据 fail 指针跳转到最接近的备选位置——就像你在打字时打错了一个字母，不需要把整个词删掉重打，而是根据词典提示跳到最可能的修正位置。

📝 算法流程

1. 将所有模式串插入 Trie 树
2. BFS 构建 fail 指针：
3. 根节点的子节点的 fail 指向根
4. 对于节点 u 和字符 c：如果 u 有 c 子节点 v，则 fail[v] = go(fail[u], c)
5. 如果 u 没有 c 子节点，则 go(u, c) = go(fail[u], c)（自动机转移）
6. 在主串上按自动机转移，每到一个节点就输出该节点及其 fail 链上的所有模式串

$$\text{时间：}O(|S| + \sum |P_i| + \text{匹配次数})$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

struct ACAutomaton {
    static const int SIGMA = 26;
    struct Node {
        int next[SIGMA];
        int fail;
        int count; // 以该节点结尾的模式串数量
        Node() { memset(next, 0, sizeof(next)); fail = 0; count = 0; }
    };
    vector nodes;
    
    ACAutomaton() { nodes.emplace_back(); } // root = 0
    
    void insert(const string& s) {
        int u = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (!nodes[u].next[idx]) {
                nodes[u].next[idx] = nodes.size();
                nodes.emplace_back();
            }
            u = nodes[u].next[idx];
        }
        nodes[u].count++;
    }
    
    void build() {
        queue q;
        for (int c = 0; c < SIGMA; c++)
            if (nodes[0].next[c]) q.push(nodes[0].next[c]);
        
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int c = 0; c < SIGMA; c++) {
                int v = nodes[u].next[c];
                if (v) {
                    nodes[v].fail = nodes[nodes[u].fail].next[c];
                    nodes[v].count += nodes[nodes[v].fail].count;
                    q.push(v);
                } else {
                    nodes[u].next[c] = nodes[nodes[u].fail].next[c];
                }
            }
        }
    }
    
    int query(const string& s) {
        int u = 0, res = 0;
        for (char c : s) {
            u = nodes[u].next[c - 'a'];
            res += nodes[u].count;
        }
        return res;
    }
};

int main() {
    ACAutomaton ac;
    ac.insert("he");
    ac.insert("she");
    ac.insert("his");
    ac.insert("hers");
    ac.build();
    cout << ac.query("ushers") << endl; // 3 ("she", "he", "hers")
    return 0;
}

⚠️ 常见坑点

📚 相关题目