hdu 2222 ac自动机更新模板 for onSite contest

http://acm.split.hdu.edu.cn/showproblem.php?pid=2222

#include <cstdio>
#include <cstdlib>
#include <cstring>
const int maxn = 1000000 + 20;
const int N = 26;

struct AC {
    int son[maxn][N], fail[maxn * N], endPos[maxn * N];
    int t, root;
    int create() {
        ++t;
        for (int i = 0; i < N; ++i) son[t][i] = NULL;
        fail[t] = endPos[t] = NULL;
        return t;
    }
    void init() {
        t = 0;
        root = create();
    }
    int getID(char ch) {
        return ch - 'a';
    }
    void toInsert(char str[]) {
        int now = root;
        for (int i = 1; str[i]; ++i) {
            int id = getID(str[i]);
            if (son[now][id] == NULL) son[now][id] = create();
            now = son[now][id];
        }
        endPos[now]++;
    }
    int que[maxn * N];
    void buildFail() {
        fail[root] = root;
        int head = 0, tail = 0;
        for (int i = 0; i < N; ++i) {
            if (son[root][i] == NULL) son[root][i] = root;
            else {
                fail[son[root][i]] = root;
                que[tail++] = son[root][i];
            }
        }
        while (head < tail) {
            int cur = que[head++];
            for (int i = 0; i < N; ++i) {
                if (son[cur][i] == NULL) son[cur][i] = son[fail[cur]][i];
                else {
                    fail[son[cur][i]] = son[fail[cur]][i]; //虚拟边已经存在
                    que[tail++] = son[cur][i];
                }
            }
        }
    }
    int query(char str[]) {
        int now = root, ans = 0;
        for (int i = 1; str[i]; ++i) {
            int id = getID(str[i]);
            now = son[now][id];
            int p = now;
            while (p != root && endPos[p] != -1) {
                ans += endPos[p];
                endPos[p] = -1;
                p = fail[p];
            }
        }
        return ans;
    }
} ac;

char str[maxn];
void work () {
    ac.init();
    int n;
    scanf("%d", &n);
    while (n--) {
        scanf("%s", str + 1);
        ac.toInsert(str);
    }
    scanf("%s", str + 1);
    ac.buildFail();
    printf("%d
", ac.query(str));
    return ;
}
int main() {
    #ifdef local
    freopen("data.txt", "r", stdin);
    #endif
    int t;
    scanf("%d", &t);
    while (t--) {
        work ();
    }
    return 0;
}