AC 自动机主要有3个步骤：
- 构造trie树
- 在trie树的基础上，添加失败指针，其添加方法就是一句话：由父亲节点开始，沿着失败指针向上找，一直找到一个节点p的next[i]不为空或者到根节点，把当前节点的next[i]的失败指针指向p的next[i]
- 进行模式串的匹配
hdu 2222 代码，可兼作模板：
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
|
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <iostream>
using namespace std;
const int maxint = -1u >> 1;
string image;
string strs[10010];
struct Node
{
Node *next[26];
Node *fail;
int count;
Node()
{
fail = NULL;
memset(next, NULL, sizeof(next));
count = 0;
}
} q[500010];
Node *root;
void insert(string str, Node *root)
{
Node *p = root;
int i = 0, index;
while (str[i])
{
index = str[i] - 'a';
if (p->next[index] == NULL)
p->next[index] = new Node();
p = p->next[index];
i++;
}
p->count++;
}
void buildfail(Node *root)
{
int i;
root->fail = NULL;
int head, tail;
head = tail = 0;
q[head++] = root;
while (head != tail)
{
Node *tmp = q[tail++];
Node *p = NULL;
for (int i = 0; i < 26; i++)
{
if (tmp->next[i] != NULL)
{
if (tmp == root)
tmp->next[i]->fail = root;
else
{
p = tmp->fail;
while (p != NULL)
{
if (p->next[i] != NULL)
{
tmp->next[i]->fail = p->next[i];
break;
}
p = p->fail;
}
if (p == NULL)
tmp->next[i]->fail = root;
}
q[head++] = tmp->next[i];
}
}
}
}
int query(Node *root)
{
int i = 0, cnt = 0, index, len = image.size();
Node *p = root;
while (image[i])
{
index = image[i] - 'a';
while (p->next[index] == NULL && p != root)
p = p->fail;
p = p->next[index];
p = (p == NULL) ? root : p;
Node *tmp = p;
while (tmp != root && tmp->count != -1)
{
cnt += tmp->count;
tmp->count = -1;
tmp = tmp->fail;
}
i++;
}
return cnt;
}
int main()
{
#ifndef ONLINE_JUDGE freopen("f:/in.txt", "r", stdin);
#endif ios::sync_with_stdio(0);
int T;
cin >> T;
while (T--)
{
root = new Node();
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> strs[i];
cin >> image;
for (int i = 0; i < n; i++)
{
insert(strs[i], root);
}
buildfail(root);
cout << query(root) << endl;
}
return 0;
}
|
详细的参看：http://www.cppblog.com/mythit/archive/2009/04/21/80633.html