AC自动机

Aho-Corasick automaton，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法。

多模匹配：从一段字符串中匹配多个模式字符串。

前置知识：

1. 字典树（Trie）与双数组字典树（Double-Array-Trie） 字典树用于单模匹配场景。
2. 字符串匹配 – KMP算法

AC自动机算法分为三步：构造一棵Trie树，构造失败指针和模式匹配过程。

当我们的模式串在Trie上进行匹配时，如果与当前节点的关键字不能继续匹配，就应该去当前节点的失败指针所指向的节点继续进行匹配。

例如，以say、she、shr、he、her构建trie树，构造的失败指针如下图所示：

AC自动机代码示例：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <unordered_set>
using namespace std;

#define BASE 26

// 定义节点的数据结构
struct Node {
    Node() : flag(false), fail(nullptr) {
        for (int i = 0; i < BASE; i++) next[i] = nullptr;
        return ;
    }
    string *s; // 记录节点存储的字符串值
    bool flag;
    Node *fail;
    Node *next[BASE];
};

struct Automaton {
public :
    Automaton() = default;

    // 构造trie
    void insert(string s) {
        Node *p = &root;
        for (auto x : s) {
            int ind = x - 'a';
            if (p->next[ind] == nullptr) p->next[ind] = new Node();
            p = p->next[ind];
        }
        if (p->flag == false) {
            p->flag = true;
            p->s = new string(s);
        }
        return ;
    }
    // 在trie上构造AC自动机的失败指针
    void build_ac() {
        queue<Node *> q;
        // 层序遍历第二层 失败指针指向root
        for (int i = 0; i < BASE; i++) {
            if (root.next[i] == nullptr) continue;
            root.next[i]->fail = &root;
            q.push(root.next[i]);
        }
        while (!q.empty()) {
            // p: 记录当前被计算的节点，其fail指针应该指向哪里
            Node *now = q.front(), *p; 
            q.pop();
            for (int i = 0; i < BASE; i++) {
                if (now->next[i] == nullptr) continue;
                // p指向其父节点的fail节点
                p = now->fail; 
                // 例：s->h->e失配时，看是否有h->e
                // 例：如果没有h->e，则查看是否有e
                while (p && p->next[i] == nullptr) p = p->fail; 
                // 例：有则把s->h->e的fail指向h->e
                // 如果p没有指向nullptr（root->fail）证明在trie中存在字符串的一个子串（最长子串）
                if (p) p = p->next[i];
                // 例：如果没有e 则p指向root
                else p = &root;
                now->next[i]->fail = p;
                q.push(now->next[i]);
            }
        }
        return ;
    }
    /**
    * 对字符串s进行多模匹配
    * 返回匹配到的所有模式串
    **/
    unordered_set<string> match(string &s) {
        int cnt = 0;
        unordered_set<string> ret;
        Node *p = &root, *k;
        for (auto x : s) {
            // 状态转移
            int ind = x - 'a';
            // 如果失配 p转移到fail
            while (p && p->next[ind] == nullptr) p = p->fail, cnt += 1;
            // 如果匹配到p向下走到目标节点
            if (p) p = p->next[ind], cnt += 1;
            // 匹配失败 p回到root
            else p = &root, cnt += 1;
            // 提取结果
            k = p;
            while (k) {
                // 如果匹配成功s->h->e 则一定能够匹配成功h->e、 e
                if (k->flag) ret.insert(*(k->s));
                k = k->fail;
            }
        }
        cout << "Total operator : " << cnt << endl;
        return ret;
    }
private:
    Node root;
};

int main() {
    int n;
    Automaton tree;
    string s;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s;
        tree.insert(s);
    }
    tree.build_ac();
    cin >> s;
    auto ans = tree.match(s);
    for (auto x : ans) cout << x << endl; 
    cout << "find : " << ans.size() << " item(s)" << endl;
    return 0;
}

AC自动机的优化

利用空节点，使当前节点的空子节点 指向其fail节点的 子节点，减少匹配次数。

优化AC自动机代码示例：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <unordered_set>
using namespace std;

#define BASE 26
struct Node {
    Node() : flag(false), fail(nullptr) {
        for (int i = 0; i < BASE; i++) next[i] = nullptr;
        return ;
    }
    string *s;
    bool flag;
    Node *fail;
    Node *next[BASE];
};

struct Automaton {
public :
    Automaton() = default;
    void insert(string s) {
        Node *p = &root;
        for (auto x : s) {
            int ind = x - 'a';
            if (p->next[ind] == nullptr) p->next[ind] = new Node();
            p = p->next[ind];
        }
        if (p->flag == false) {
            p->flag = true;
            p->s = new string(s);
        }
        return ;
    }
    void build_ac() {
        queue<Node *> q;
        for (int i = 0; i < BASE; i++) {
            if (root.next[i] == nullptr) {
                root.next[i] = &root; // 让根节点的空边 都指向根节点
                continue;
            }
            root.next[i]->fail = &root;
            q.push(root.next[i]);
        }
        while (!q.empty()) {
            Node *now = q.front(); 
            q.pop();
            for (int i = 0; i < BASE; i++) {
                if (now->next[i] == nullptr) {
                    now->next[i] = now->fail->next[i]; // 层序遍历时 若当前节点的第i条边是空的 则当前节点的第i条边指向当前节点fail指针的第i条边
                    continue; 
                }
                now->next[i]->fail = now->fail->next[i]; // 可以保证now->fail->next[i]不会是nullptr
                q.push(now->next[i]);
            }
        }
        return ;
    }
    unordered_set<string> match(string &s) {
        int cnt = 0;
        unordered_set<string> ret;
        Node *p = &root, *k;
        for (auto x : s) {
            // 状态转移
            int ind = x - 'a';
            p = p->next[ind], cnt += 1;
            // 提取结果
            k = p;
            while (k) {
                if (k->flag) ret.insert(*(k->s));
                k = k->fail;
            }
        }
        cout << "Total operator : " << cnt << endl;
        return ret;
    }
private:
    Node root;
};

int main() {
    int n;
    Automaton tree;
    string s;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s;
        tree.insert(s);
    }
    tree.build_ac();
    cin >> s;
    auto ans = tree.match(s);
    for (auto x : ans) cout << x << endl;
    cout << "find : " << ans.size() << " item(s)" << endl;
    return 0;
}