帮我写一个ac自动模板

好的，我可以为您提供 AC 自动机的模板。

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;
int tr[N][26], fail[N], tot = 0;
bool end[N];
vector<int> g[N];

void insert(string s) {
    int u = 0;
    for (int i = 0; i < s.size(); i++) {
        int c = s[i] - 'a';
        if (!tr[u][c]) tr[u][c] = ++tot;
        u = tr[u][c];
    }
    end[u] = true;
}

void build() {
    queue<int> q;
    for (int i = 0; i < 26; i++) {
        if (tr[0][i]) q.push(tr[0][i]);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < 26; i++) {
            if (tr[u][i]) {
                fail[tr[u][i]] = tr[fail[u]][i];
                q.push(tr[u][i]);
                g[fail[tr[u][i]]].push_back(tr[u][i]);
            } else {
                tr[u][i] = tr[fail[u]][i];
            }
        }
    }
}

void match(string s) {
    int u = 0;
    for (int i = 0; i < s.size(); i++) {
        int c = s[i] - 'a';
        u = tr[u][c];
        int tmp = u;
        while (tmp != 0) {
            if (end[tmp]) cout << i - g[tmp].size() + 1 << endl;
            tmp = fail[tmp];
        }
    }
}

int main() {
    string str;
    cin >> str;
    int n;
    cin >> n;
    while (n--) {
        string patt;
        cin >> patt;
        insert(patt);
    }
    build();
    match(str);
    return 0;
}

这是 AC 自动机的基本模板，您可以根据需要进行更改。