每次第一道模板题都是非常有意义的，考试前夕费尽心思学了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;} |
原文：http://www.cnblogs.com/chanme/p/3532917.html