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

1struct tnode {
2    int s;
3    tnode *f, *w, *c[26];
4} T[5000000], *Q[5000000];
5int C;

1inline tnode *tnew() {
2    memset(T + C, 0, sizeof(tnode));
3    return T + C++;
4}

 1inline void AcaInsert(tnode *p, const char *s) {
 2    while (*s) {
 3        int u = *s - 'a';
 4        if (!p->c[u])
 5            p->c[u] = tnew();
 6        p = p->c[u];
 7        ++s;
 8    }
 9    ++p->s;
10}

 1inline void AcaBuild(tnode *p) {
 2    p->f = p->w = p;
 3    int ql = 0;
 4    for (int i = 0; i < 26; ++i)
 5        if (p->c[i]) {
 6            p->c[i]->f = p->c[i]->w = p;
 7            Q[ql++] = p->c[i];
 8        }
 9    for (int qf = 0; qf < ql; ++qf)
10        for (int i = 0; i < 26; ++i)
11            if (Q[qf]->c[i]) {
12                tnode *f = Q[qf]->f;
13                while (f != p && !f->c[i])
14                    f = f->f;
15                if (f->c[i]) {
16                    Q[qf]->c[i]->f = f->c[i];
17                    Q[qf]->c[i]->w = f->c[i]->s ? f->c[i] : f->c[i]->w;
18                }
19                else
20                    Q[qf]->c[i]->f = Q[qf]->c[i]->w = p;
21                Q[ql++] = Q[qf]->c[i];
22            }
23}

 1inline int AcaMatch(tnode *root, const char *s) {
 2    int x = 0;
 3    for (tnode *p = root; *s; ++s) {
 4        while (p != root && !p->c[*s - 'a'])
 5            p = p->f;
 6        if (p->c[*s - 'a']) {
 7            p = p->c[*s - 'a'];
 8            for (tnode *q = p; q->s != -1; q = q->w) {
 9                x += q->s;
10                q->s = -1;
11            }
12        }
13    }
14    return x;
15}

 1int main() {
 2    int tt;
 3    scanf("%d", &tt);
 4    while (tt--) {
 5        C = 0;
 6        tnode *root = tnew();
 7        root->s = -1;
 8        int N;
 9        scanf("%d", &N);
10        while (N--) {
11            scanf("%s", S);
12            AcaInsert(root, S);
13        }
14        AcaBuild(root);
15        scanf("%s", S);
16        printf("%d\n", AcaMatch(root, S));
17    }
18    return 0;
19}