看了别人写的AC自动机，瞬时觉得自己写的好难看，于是决定改写一下，贴一下模板，以后备用
|
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 |
#define maxn 220000#define ll long longint n, m;struct
Trie{ Trie *fail, *go[26]; bool
ter; void
init(){ memset(go, 0, sizeof(go)); fail = NULL; ter = false; }}pool[maxn], *root;int
tot;void
insert(char
*c){ int
len = strlen(c); Trie *p = root; for
(int i = 0; i < len; i++){ if
(p->go[c[i] - ‘a‘] != 0) p = p->go[c[i] - ‘a‘]; else{ pool[tot].init(); p->go[c[i] - ‘a‘] = &pool[tot++]; p = p->go[c[i] - ‘a‘]; } } p->ter = true;}void
getFail(){ queue<Trie*> que; root->fail = root; for
(int i = 0; i < 26; i++){ if
(root->go[i]) { que.push(root->go[i]); root->go[i]->fail = root; } else{ root->go[i] = root; } } while
(!que.empty()){ Trie *p = que.front(); que.pop(); for
(int i = 0; i < 26; i++){ if
(p->go[i]){ que.push(p->go[i]); p->go[i]->fail = p->fail->go[i]; p->go[i]->ter |= p->go[i]->fail->ter; } else{ p->go[i] = p->fail->go[i]; } } }} |
原文：http://www.cnblogs.com/chanme/p/3670026.html