AC自动机 这个也可以拿来做模板了，使用静态数组模拟建树
1 //#pragma comment(linker, "/STACK:1677721600")
2 #include <map>
3 #include <set>
4 #include <stack>
5 #include <queue>
6 #include <cmath>
7 #include <ctime>
8 #include <vector>
9 #include <cstdio>
10 #include <cctype>
11 #include <cstring>
12 #include <cstdlib>
13 #include <iostream>
14 #include <algorithm>
15 using namespace std;
16 #define INF 0x3f3f3f3f
17 #define inf (-((LL)1<<40))
18 #define lson k<<1, L, (L + R)>>1
19 #define rson k<<1|1, ((L + R)>>1) + 1, R
20 #define mem0(a) memset(a,0,sizeof(a))
21 #define mem1(a) memset(a,-1,sizeof(a))
22 #define mem(a, b) memset(a, b, sizeof(a))
23 #define FIN freopen("in.txt", "r", stdin)
24 #define FOUT freopen("out.txt", "w", stdout)
25 #define rep(i, a, b) for(int i = a; i <= b; i ++)
26 #define dec(i, a, b) for(int i = a; i >= b; i --)
27
28 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
29 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
30 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
31 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b; }
32
33 //typedef __int64 LL;
34 typedef long long LL;
35 const int MAXN = 1000 + 100;
36 const int MAXM = 2000000 + 100;
37 const double eps = 1e-8;
38 LL MOD = 1000000007;
39
40
41 const int SIGMA_SIZE = 27;
42 const int MAX_LEN = 52;
43
44 struct ACMachine {
45 int ch[MAXN * MAX_LEN][SIGMA_SIZE];
46 int val[MAXN * MAX_LEN];
47 int fail[MAXN * MAX_LEN];
48 int last[MAXN * MAX_LEN];
49
50 int id[MAXN * MAX_LEN], ans[MAXN];
51
52 int node_cnt;
53 queue<int>q;
54
55 void init() {
56 node_cnt = 0;
57 mem0(ch); mem0(val);
58 mem0(fail); mem0(last);
59 while(!q.empty()) q.pop();
60 }
61 int get_idx(char ch) {
62 if(ch >= 'A' && ch <= 'Z')
63 return ch - 'A';
64 return 26;
65 }
66 void insert_to_tree(char *str, int p) {
67 int u = 0, len = strlen(str);
68 rep (i, 0, len - 1) {
69 int c = get_idx(str[i]);
70 if(!ch[u][c]) {
71 ch[u][c] = ++node_cnt;
72 }
73 u = ch[u][c];
74 }
75 val[u] ++;
76
77 id[u] = p;
78 }
79 void get_fail() {
80 rep (c, 0, SIGMA_SIZE - 1) {
81 int u = ch[0][c];
82 if(u) q.push(u);
83 }
84 while(!q.empty()) {
85 int r = q.front(); q.pop();
86 rep (c, 0, SIGMA_SIZE - 1) {
87 int u = ch[r][c];
88 if(!u) {
89 ch[r][c] = ch[fail[r]][c];
90 continue;
91 }
92 q.push(u);
93 int v = fail[r];
94 while(v && !ch[v][c]) v = fail[v];
95 fail[u] = ch[v][c];
96 last[u] = val[fail[u]] ? fail[u] : last[fail[u]];
97 }
98 }
99 }
100 void find_ans(char *str) {
101
102 mem0(ans);
103
104 int len = strlen(str), u = 0;
105 rep(i, 0, len - 1) {
106 int c = get_idx(str[i]);
107 u = ch[u][c];
108 int v = u;
109 while(v) {
110 if(val[v]) {
111 ans[id[u]] ++;
112 }
113 v = last[v];
114 }
115 }
116
117 }
118 }acm;
119
120 int n;
121 char str[MAXM], s[MAXN][MAX_LEN];
122
123 int main()
124 {
125 // FIN;
126 while(~scanf("%d%*c", &n)) {
127 acm.init();
128 rep (i, 1, n) {
129 scanf("%s", s[i]);
130 acm.insert_to_tree(s[i], i);
131 }
132 acm.get_fail();
133 scanf("%s", str);
134 acm.find_ans(str);
135 rep (i, 1, n) if(acm.ans[i]){
136 printf("%s: %d\n", s[i], acm.ans[i]);
137 }
138 }
139 return 0;
140 }