用C++实现AC自动机

AC自动机是一种高效的字符串匹配算法，它可以在一个文本串中同时匹配多个模式串。下面给出用C++实现AC自动机的代码：

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 100010;
const int MAXM = 26;

struct TrieNode {
    int fail, next[MAXM];
    bool isEnd;
    int id;
} trie[MAXN];

int cnt = 0;

void insert(string str, int id) {
    int len = str.length();
    int p = 0;
    for (int i = 0; i < len; i++) {
        int c = str[i] - 'a';
        if (trie[p].next[c] == 0) {
            trie[++cnt].fail = 0;
            memset(trie[cnt].next, 0, sizeof(trie[cnt].next));
            trie[cnt].isEnd = false;
            trie[cnt].id = 0;
            trie[p].next[c] = cnt;
        }
        p = trie[p].next[c];
    }
    trie[p].isEnd = true;
    trie[p].id = id;
}

void buildAC() {
    queue<int> Q;
    for (int i = 0; i < MAXM; i++) {
        if (trie[0].next[i] != 0) {
            Q.push(trie[0].next[i]);
        }
    }
    while (!Q.empty()) {
        int p = Q.front();
        Q.pop();
        for (int i = 0; i < MAXM; i++) {
            if (trie[p].next[i] != 0) {
                int fail = trie[p].fail;
                while (fail != 0 && trie[fail].next[i] == 0) {
                    fail = trie[fail].fail;
                }
                trie[trie[p].next[i]].fail = trie[fail].next[i];
                Q.push(trie[p].next[i]);
            }
        }
    }
}

void searchAC(string str) {
    int len = str.length();
    int p = 0;
    for (int i = 0; i < len; i++) {
        int c = str[i] - 'a';
        while (p != 0 && trie[p].next[c] == 0) {
            p = trie[p].fail;
        }
        p = trie[p].next[c];
        if (trie[p].isEnd) {
            cout << "匹配到模式串：" << trie[p].id << endl;
        }
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string str;
        cin >> str;
        insert(str, i);
    }
    buildAC();
    string text;
    cin >> text;
    searchAC(text);
    return 0;
}

该代码中，TrieNode结构体表示Trie树的节点，fail表示该节点的失败指针，next表示该节点的子节点，isEnd表示该节点是否为某个模式串的结尾，id表示该节点所代表的模式串的编号。insert函数用于向Trie树中插入一个字符串，buildAC函数用于构建AC自动机，searchAC函数用于在文本串中搜索模式串。在主函数中，先读入模式串的数量和内容，然后构建AC自动机，最后读入文本串并搜索模式串。