每次第一道模板题都是非常有意义的，考试前夕费尽心思学了KMP，学了Trie树，就是为了学这个做铺垫的，这道题时著名的AC自动机模板题。个人理解AC自动机就是在一棵Trie树上求失配指针，然后实现了多模匹配。只需遍历一次文本串就能求出所有的内容。在下面的query代码里，因为不能重复计算相同的模板串，所以每次加上后temp->count=-1，表示已经算过，在while循环里temp->count!=-1的时候才进行失配其实是有意义的，当temp->count==-1时说明已经沿着失配指针匹配过一次了，所以就没有必要再往上跑一次。假如每次匹配完我令temp->count=0，然后while循环里少了temp->count!=-1的话也是可以过的，前者200ms,后者600ms，就是因为多了不必要的计算。下面贴一记代码
|
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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
//// main.cpp// AC auto machine//// Created by change on 14-1-24.// Copyright (c) 2014年 chanme. All rights reserved.//#include <iostream>#include <cstring>#include <queue>#include <cstdio>#include <algorithm>#define MAXCHAR 26#define maxn 500000using
namespace
std;
struct
TrieNode
{ int
count;
TrieNode* next[MAXCHAR];
TrieNode* fail;
void
init()
{
memset(next,0,sizeof(next));
fail=NULL;
count=0;
}
}T[maxn],*Trie;int
top;
void
insert(char
*c)
{ int
len=(int)strlen(c);TrieNode *p=Trie;
for(int
i=0;i<len;i++){
if(p->next[c[i]-‘a‘]!=NULL){
p=p->next[c[i]-‘a‘];
}
else{
T[top].init();
p->next[c[i]-‘a‘]=&T[top++];
p=p->next[c[i]-‘a‘];
}
}
p->count++;
}void
getFail()
{ queue<TrieNode *> que; // 用于BFS的队列
que.push(Trie); // 将根结点压入
Trie->fail=NULL; // 根结点的失配指针为NULL
while(!que.empty())
{
TrieNode* temp=que.front();
que.pop();
TrieNode* p=NULL;
// 枚举每个后继
for(int
i=0;i<MAXCHAR;i++){
// 后继非空时计算其失配指针
if(temp->next[i]!=NULL) {
// 根结点的所有后继的失配指针指向根结点
if(temp==Trie){
temp->next[i]->fail=Trie;
}
else{
// 否则的话，沿着失配指针走，遇到有相同后继的则连失配指针
p=temp->fail;
while(p!=NULL){
if(p->next[i]!=NULL){
temp->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
// 否则也指向根结点
if(p==NULL) temp->next[i]->fail=Trie;
}
// 压入队列
que.push(temp->next[i]);
}
}
}
}int
query(char
*c)
{ int
len=(int)strlen(c);
int
res=0;
TrieNode *p=Trie;
for(int
i=0;i<len;i++){
while(p->next[c[i]-‘a‘]==NULL && p!=Trie) p=p->fail;
p=p->next[c[i]-‘a‘];
if(p==NULL) p=Trie;
TrieNode *temp=p;
while(temp!=Trie&&temp->count!=-1){
res+=temp->count;
temp->count=-1;
temp=temp->fail;
}
}
return
res;
}char
str[55];
char
text[1005000];
int
n;
int
main()
{ int
cas;cin>>cas;
while(cas--)
{
top=0;T[top].init();
Trie=&T[top++];
cin>>n;
for(int
i=0;i<n;i++){
scanf("%s",str);
insert(str);
}
getFail();
scanf("%s",text);
printf("%d\n",query(text));
}
return
0;
} |