AC自动机-学习笔记

AC自动机（Aho-Corasick自动机）是一种用于字符串搜索的算法，可以在一组字符串中快速查找一个或多个子串。这种算法特别适合于在大量文本中查找多个模式。

基本概念

AC自动机结合了两种算法：Trie树和KMP算法。

• Trie树：用于存储多个字符串的数据结构，每个节点代表一个字符，从根到某一节点的路径代表一个字符串。
• KMP算法：一种字符串搜索算法，可以在不回溯文本指针的情况下，通过回溯模式指针来提高搜索效率。

构建AC自动机

构建AC自动机分为三个步骤：

1. 构建Trie树：将所有模式串插入Trie树中。
2. 构建失败指针：类似于KMP中的next数组，当节点匹配失败时，失败指针指向一个最长可匹配的后缀节点。
3. 搜索状态转移：利用Trie树和失败指针进行状态转移，匹配文本串。

构建Trie树

struct TrieNode {
    TrieNode* children[26];
    TrieNode* fail; // 失败指针
    int end; // 标记字符串结束
    TrieNode() : fail(nullptr), end(0) {
        memset(children, 0, sizeof(children));
    }
};

void insert(TrieNode* root, const string& word) {
    TrieNode* node = root;
    for (char c : word) {
        if (!node->children[c - 'a']) {
            node->children[c - 'a'] = new TrieNode();
        }
        node = node->children[c - 'a'];
    }
    node->end += 1; // 标记单词结束
}

构建失败指针

void buildFailPointer(TrieNode* root) {
    queue<TrieNode*> q;
    root->fail = nullptr;
    q.push(root);

    while (!q.empty()) {
        TrieNode* current = q.front();
        q.pop();

        for (int i = 0; i < 26; ++i) {
            TrieNode* child = current->children[i];
            if (child) {
                TrieNode* fail = current->fail;
                while (fail && !fail->children[i]) {
                    fail = fail->fail;
                }
                child->fail = fail ? fail->children[i] : root;
                q.push(child);
            }
        }
    }
}

搜索状态转移

void search(TrieNode* root, const string& text) {
    TrieNode* node = root;
    for (char c : text) {
        while (node && !node->children[c - 'a']) {
            node = node->fail; // 失败指针回溯
        }
        node = node ? node->children[c - 'a'] : root;
        for (TrieNode* temp = node; temp; temp = temp->fail) {
            if (temp->end) {
                // 找到一个模式串
            }
        }
    }
}

总结

AC自动机是一种高效的多模式字符串搜索算法，通过结合Trie树和KMP算法的优点，能够在 \(O(n)\)的时间复杂度内完成搜索。在实际应用中，AC自动机常用于文本过滤、搜索引擎等领域。

以上就是AC自动机的基本介绍和实现。希望这份学习笔记对你有所帮助！