用c++实现自动AC机

AC自动机是一种字符串匹配算法，可以用来在一个长文本串中查找多个模式串。C++中可以用Trie树和AC自动机实现，以下是AC自动机的实现代码：

1. 定义Trie树结构体

const int MAXN = 100010;

struct Trie {
    int ch[MAXN][26], val[MAXN], sz;

    void insert(char* s, int v) {
        int u = 0, n = strlen(s);
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'a';
            if (!ch[u][c]) ch[u][c] = ++sz;
            u = ch[u][c];
        }
        val[u] = v;
    }
};

2. 构建AC自动机

void build_ac(Trie& tr) {
    queue<int> q;
    for (int i = 0; i < 26; i++) {
        if (tr.ch[0][i]) q.push(tr.ch[0][i]);
    }

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < 26; i++) {
            int v = tr.ch[u][i];
            if (v) {
                q.push(v);
                tr.val[v] |= tr.val[tr.ch[u][i]];
                tr.ch[u][i] = tr.ch[tr.ch[u][i]][i];
            } else {
                tr.ch[u][i] = tr.ch[tr.ch[u][0]][i];
            }
        }
    }
}

3. AC自动机匹配

void match(Trie& tr, char* s) {
    int u = 0, n = strlen(s);
    for (int i = 0; i < n; i++) {
        int c = s[i] - 'a';
        u = tr.ch[u][c];
        if (tr.val[u]) {
            // 匹配到了模式串
        }
    }
}

完整代码如下：

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

const int MAXN = 100010;

struct Trie {
    int ch[MAXN][26], val[MAXN], sz;

    void insert(char* s, int v) {
        int u = 0, n = strlen(s);
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'a';
            if (!ch[u][c]) ch[u][c] = ++sz;
            u = ch[u][c];
        }
        val[u] = v;
    }
};

void build_ac(Trie& tr) {
    queue<int> q;
    for (int i = 0; i < 26; i++) {
        if (tr.ch[0][i]) q.push(tr.ch[0][i]);
    }

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < 26; i++) {
            int v = tr.ch[u][i];
            if (v) {
                q.push(v);
                tr.val[v] |= tr.val[tr.ch[u][i]];
                tr.ch[u][i] = tr.ch[tr.ch[u][i]][i];
            } else {
                tr.ch[u][i] = tr.ch[tr.ch[u][0]][i];
            }
        }
    }
}

void match(Trie& tr, char* s) {
    int u = 0, n = strlen(s);
    for (int i = 0; i < n; i++) {
        int c = s[i] - 'a';
        u = tr.ch[u][c];
        if (tr.val[u]) {
            // 匹配到了模式串
        }
    }
}

int main() {
    Trie tr;
    char s[MAXN];
    int n, m;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        tr.insert(s, 1 << (i - 1));
    }
    build_ac(tr);
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> s;
        match(tr, s);
    }
    return 0;
}