0%

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;
}