hdu 2222 Keywords Search ac自动机模板

题目链接

先整理一发ac自动机模板..

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <complex>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

#define rson m+1, r, rt<<1|1

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef complex <double> cmx;

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-8;

const int mod = 1e9+7;

const int inf = 1061109567;

const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

const int maxn = 5e5+5;

struct AC

{

    int nxt[maxn][26], fail[maxn], end[maxn];

    int root, len;

    int node() {

        mem1(nxt[len]);

        end[len++] = 0;

        return len-1;

    }

    void init() {

        len = 0;

        root = node();

    }

    void insert(char str[]) {

        int l = strlen(str);

        int now = root;

        for(int i = 0; i < l; i++) {

            if(nxt[now][str[i]-'a'] == -1) {

                nxt[now][str[i]-'a'] = node();

            }

            now = nxt[now][str[i]-'a'];

        }

        end[now]++;

    }

    void build() {

        queue <int> q;

        fail[root] = root;

        for(int i = 0; i < 26; i++) {

            if(nxt[root][i] == -1) {

                nxt[root][i] = root;

            } else {

                fail[nxt[root][i]] = root;

                q.push(nxt[root][i]);

            }

        }

        while(!q.empty()) {

            int now = q.front(); q.pop();

            for(int i = 0; i < 26; i++) {

                if(nxt[now][i] == -1) {

                    nxt[now][i] = nxt[fail[now]][i];

                } else {

                    fail[nxt[now][i]] = nxt[fail[now]][i];

                    q.push(nxt[now][i]);

                }

            }

        }

    }

    int query(char str[]) {

        int l = strlen(str);

        int now = root, ans = 0;

        for(int i = 0; i < l; i ++) {

            now = nxt[now][str[i]-'a'];

            int tmp = now;

            while(tmp != root) {

                ans += end[tmp];

                end[tmp] = 0;

                tmp = fail[tmp];

            }

        }

        return ans;

    }

}ac;

char s[1000005];

int main()

{

    int t, n;

    cin>>t;

    while(t--) {

        ac.init();

        scanf("%d", &n);

        for(int i = 0; i < n; i++) {

            scanf("%s", s);

            ac.insert(s);

        }

        ac.build();

        scanf("%s", s);

        printf("%d\n", ac.query(s));

    }

    return 0;

}