ac自动机模板by Lalatina （hdu 2222）

 1#include <cstdio>
 2#include <cstring>
 3
 4using namespace std;
 5
 6struct tnode {
 7    int s;
 8    tnode *f, *w, *c[26];
 9} T[5000000], *Q[5000000];
10int C;
11
12inline tnode *tnew() {
13    memset(T + C, 0, sizeof(tnode));
14    return T + C++;
15}
16
17inline void AcaInsert(tnode *p, const char *s) {
18    while (*s) {
19        int u = *s - 'a';
20        if (!p->c[u])
21            p->c[u] = tnew();
22        p = p->c[u];
23        ++s;
24    }
25    ++p->s;
26}
27
28inline void AcaBuild(tnode *p) {
29    p->f = p->w = p;
30    int ql = 0;
31    for (int i = 0; i < 26; ++i)
32        if (p->c[i]) {
33            p->c[i]->f = p->c[i]->w = p;
34            Q[ql++] = p->c[i];
35        }
36    for (int qf = 0; qf < ql; ++qf)
37        for (int i = 0; i < 26; ++i)
38            if (Q[qf]->c[i]) {
39                tnode *f = Q[qf]->f;
40                while (f != p && !f->c[i])
41                    f = f->f;
42                if (f->c[i]) {
43                    Q[qf]->c[i]->f = f->c[i];
44                    Q[qf]->c[i]->w = f->c[i]->s ? f->c[i] : f->c[i]->w;
45                }
46                else
47                    Q[qf]->c[i]->f = Q[qf]->c[i]->w = p;
48                Q[ql++] = Q[qf]->c[i];
49            }
50}
51
52inline int AcaMatch(tnode *root, const char *s) {
53    int x = 0;
54    for (tnode *p = root; *s; ++s) {
55        while (p != root && !p->c[*s - 'a'])
56            p = p->f;
57        if (p->c[*s - 'a']) {
58            p = p->c[*s - 'a'];
59            for (tnode *q = p; q->s != -1; q = q->w) {
60                x += q->s;
61                q->s = -1;
62            }
63        }
64    }
65    return x;
66}
67
68char S[1000001];
69
70int main() {
71    int tt;
72    scanf("%d", &tt);
73    while (tt--) {
74        C = 0;
75        tnode *root = tnew();
76        root->s = -1;
77        int N;
78        scanf("%d", &N);
79        while (N--) {
80            scanf("%s", S);
81            AcaInsert(root, S);
82        }
83        AcaBuild(root);
84        scanf("%s", S);
85        printf("%d\n", AcaMatch(root, S));
86    }
87    return 0;
88}