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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e4+10;
const int LEN = 2e6+10;
int vi[1000];
int viru=1;
struct Aho{
struct state{
int next[26];
int fail,cnt;
}st[N];
queue<int>q;
int size;
void init(){
while(!q.empty())q.pop();
memset(vi,0,sizeof(vi));
for(int i=0;i<N;i++){
memset(st[i].next,0,sizeof(st[i].next));
st[i].fail=st[i].cnt=0;
}
size=1;
viru=1;
}
void insert(char *S){
int n = strlen(S),now=0;
for(int i=0;i<n;i++){
int c = S[i]-'A';
if(!st[now].next[c])st[now].next[c]=size++;
now=st[now].next[c];
}
st[now].cnt=viru++;
}
void build(){
for(int i=0;i<26;i++)
if(st[0].next[i])q.push(st[0].next[i]);
while(!q.empty()){
int u = q.front();q.pop();
for(int i=0;i<26;i++){
if(st[u].next[i])
st[st[u].next[i]].fail=st[st[u].fail].next[i],q.push(st[u].next[i]);
else
st[u].next[i]=st[st[u].fail].next[i];
}
}
}
void Get(int u){
while(u){
vi[st[u].cnt]++;
u=st[u].fail;
}
}
void match(char *S){
int n=strlen(S),now=0;
for(int i=0;i<n;i++){
int c = S[i]-'A';
if(!(c<=25&&c>=0)){
now=0;
continue;
}
if(st[now].next[c]){
now=st[now].next[c];
}
else {
now=st[st[now].fail].next[c];
}
if(st[now].cnt){
Get(now);
}
}
}
}aho;
char str[1010][60];
char S[LEN];
int main(){
int n;
while(scanf("%d",&n)!=EOF){
aho.init();
for(int i=1;i<=n;i++){
scanf("%s",str[i]);
aho.insert(str[i]);
}
scanf("%s",S);
aho.build();
aho.match(S);
for(int i=1;i<=n;i++)
if(vi[i])printf("%s: %d\n",str[i],vi[i]);
}
}
|