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
| #include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define maxn 200010
#define maxm 2000010
using namespace std;
int n;
char s[maxm];
#define ch s[i] - 'a'
struct AC_automaton {
int nxt[26], cnt, fail;
} T[maxn]; int top = 1, rt = 1, id[maxn];
void insert(char *s, int k) {
int now = rt, l = strlen(s);
for (int i = 0; i < l; ++i) {
if (!T[now].nxt[ch]) T[now].nxt[ch] = ++top;
now = T[now].nxt[ch];
} id[k] = now;
}
queue<int> Q; int a[maxn], c1;
void init_fail() {
for (int i = 0; i < 26; ++i) {
int u = T[rt].nxt[i];
if (!u) { T[rt].nxt[i] = rt; continue; }
T[u].fail = rt; Q.push(u);
}
while (!Q.empty()) {
int u = Q.front(); Q.pop(); a[++c1] = u;
for (int i = 0; i < 26; ++i) {
int &v = T[u].nxt[i];
if (!v) { v = T[T[u].fail].nxt[i]; continue; }
T[v].fail = T[T[u].fail].nxt[i]; Q.push(v);
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) scanf("%s", s), insert(s, i);
init_fail(); scanf("%s", s); int l = strlen(s), now = rt;
for (int i = 0; i < l; ++i) {
now = T[now].nxt[ch];
++T[now].cnt;
}
for (int i = c1, u = a[i]; i; u = a[--i])
T[T[u].fail].cnt += T[u].cnt;
for (int i = 1; i <= n; ++i) printf("%d\n", T[id[i]].cnt);
return 0;
}
|