【题意】：给出n个单词，和一个文本，单词可能会重复出现，问文本中一共出现了多少个给定的单词？
【题解】：AC自动机模板题。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 using namespace std;
5 #define maxn 700050
6 const int kind = 26;
7 int root, tot;
8 int que[maxn], head, tail;
9 int n, m;
10 char t[1005000];
11
12 struct Node {
13 int child[kind], fail, cnt;
14 void init() {
15 memset(child, 0, sizeof (child));
16 fail = -1, cnt = 0;
17 }
18 }T[maxn];
19
20 void init() {
21 root = tot = 0;
22 T[root].init();
23 }
24
25 void insert(char *s) {//插入单词
26 int p = root, index;
27 while (*s) {
28 index = *s - 'a';
29 if (!T[p].child[index]) {
30 T[++tot].init();
31 T[p].child[index] = tot;
32 }
33 p = T[p].child[index];
34 s++;
35 }
36 T[p].cnt++;
37 }
38
39 void build_ac_auto() {
40 head = tail = 0;
41 que[tail++] = root;
42 while (head < tail) {
43 int u = que[head++];
44 for (int i = 0; i < kind; i++) {
45 if (T[u].child[i]) {
46 int son = T[u].child[i];
47 int p = T[u].fail;
48 if (u == root) T[son].fail = root;
49 else T[son].fail = T[p].child[i];
50 que[tail++] = son;
51 } else {//trie图，设定虚拟节点
52 int p = T[u].fail;
53 if (u == root) T[u].child[i] = root;
54 else T[u].child[i] = T[p].child[i];
55 }
56 }
57 }
58 }
59
60 int query(char *t) {
61 int p = root, cnt = 0;
62 while(*t) {
63 int index = *t - 'a';
64 p = T[p].child[index];
65 int tmp = p;
66 while(tmp != root) {
67 cnt += T[tmp].cnt;
68 T[tmp].cnt = 0;
69 tmp = T[tmp].fail;
70 }
71 t++;
72 }
73 return cnt;
74 }
75
76 int main() {
77 int T;
78 char s[55];
79 scanf("%d", &T);
80 while(T--) {
81 scanf("%d", &n);
82 init();
83 for(int i = 0; i < n; i++) {
84 scanf("%s", s);
85 insert(s);
86 }
87 scanf("%s", t);
88 build_ac_auto();
89 int ans = query(t);
90 printf("%d\n", ans);
91 }
92 return 0;
93 }