hdu 2222

发表于 更新于

hdu 2222 AC 自动机
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2222

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <stdio.h>

#define N 500051
#define CHARSET_SIZE 26
#define NIL 0
#define ROOT 1

int alloc;
int trans[N][CHARSET_SIZE];
int fails[N];
int counts[N];

int qhead, qtail;
int queue[N];

char str[1000001];
char keyword[51];

int ac_alloc() {
    int n = alloc++;
    for (int c = 0; c < CHARSET_SIZE; c++) {
        trans[n][c] = NIL;
    }
    counts[n] = 0;
    return n;
}

void ac_insert(char *s) {
    int n = ROOT;
    for (int i = 0; s[i]; i++) {
        int c = s[i] - 'a';
        if (trans[n][c] == NIL) {
            trans[n][c] = ac_alloc();
        }
        n = trans[n][c];
    }
    counts[n]++;
}

void ac_build_fails() {
    qhead = qtail = 0;
    fails[ROOT] = NIL;
    for (int i = 0; i < CHARSET_SIZE; i++) {
        if (trans[ROOT][i] != NIL) {
            fails[trans[ROOT][i]] = ROOT;
            queue[qtail++] = trans[ROOT][i];
        }
    }
    while (qhead < qtail) {
        int n = queue[qhead++];
        for (int i = 0; i < CHARSET_SIZE; i++) {
            if (trans[n][i] == NIL) {
                continue;
            }
            int fail = fails[n];
            while (fail != NIL) {
                if (trans[fail][i] != NIL) {
                    fails[trans[n][i]] = trans[fail][i];
                    break;
                }
                fail = fails[fail];
            }
            if (fail == NIL) {
                fails[trans[n][i]] = ROOT;
            }
            queue[qtail++] = trans[n][i];
        }
    }
}

int ac_match(char *s) {
    int total = 0;
    int n = ROOT;
    for (int i = 0; s[i]; i++) {
        int c = s[i] - 'a';
        while (trans[n][c] == NIL && n != ROOT) {
            n = fails[n];
        }
        n = trans[n][c];
        if (n == NIL) {
            n = ROOT;
        }
        int t = n;
        while (t != ROOT && counts[t] != -1) {
            total += counts[t];
            counts[t] = -1;
            t = fails[t];
        }
    }
    return total;
}

int main() {
    int t;

    scanf("%d", &t);
    while (t--) {
        alloc = ROOT;
        ac_alloc();
        int w;
        scanf("%d", &w);
        while (w--) {
            scanf("%s", keyword);
            ac_insert(keyword);
        }
        ac_build_fails();
        scanf("%s", str);
        printf("%d\n", ac_match(str));
    }
    return 0;
}