ac自动机，是有穷自动机的一种，主要用来解决多模式串匹配的问题。例如给你若干个关键字he she say her shr，然后给你一篇文章（长串）
yasherhs，要求该串中总共出现了以上关键字多少次。
ac自动机主要分三步：
1、根据关键字构建trie树
2、根据trie树构造失败指针
3、在构造完失败指针的trie树上运行长串，得到结果
构建trie树可以达到O(a(m1 + m2 + ... + mi))复杂度，即为所有关键字长度的和。构建失败指针的复杂度同样平均为O(a( m1 + m2 + ... + mi))，其中a是构成字符串的字符集中字符个数。空间复杂度同样为O(a(m1 + m2 + ... + mi))。在trie树上运行长串的时间为O(n)n为长串的长度。
构建trie树的方法比较简单，就和构造多叉树类似，这里不详述了，关键就是标识出哪些字符是一个关键字的结尾，即从root节点到当前节点恰好表示一个关键字。
关键问题是构造失败指针，其实这里构造失败指针的方法和kmp基本一样，ac自动机说白了就是构造树状KMP。
上篇文章有介绍KMP求失败指针的方法，就是针对子串运行KMP算法。
ac自动机的失败指针构造有些类似，在trie树上运行一遍BFS，即可求得失败指针。
具体方法是，对当前节点p，若p的父亲节点的失败指针q的某个孩子节点表示的字符和p表示的字符相同，则p的失败指针指向q的对应的孩子，否则继续寻找q的失败指针，直到root。
构造完失败指针即可在ac自动机上匹配长串了，匹配方法如下，若当前长串a[i]与ac自动机当前节点p不匹配，则p = p->fail，继续匹配，若不匹配则继续向失败指针走，如果走到root，则从头匹配；否则若a[i]与当前节点p匹配，则查看节点p处有没有对应的关键词，若有则说明成功找到一个关键词。
下面以hdoj2222题为例看ac自动机代码，2222题是标准的多模式匹配题模版：
1 #include <cstdio>
2 #include <cstdlib>
3 #include <string.h>
4 #include <queue>
5
6 #define MAX 26
7
8 typedef struct node {
9 struct node *next;
10 struct node *children[MAX];
11 int words_amount;
12 } NODE;
13
14 static void init_node(NODE *p) {
15 p->next = NULL;
16 int i = 0;
17 for (i = 0; i < MAX; ++i) {
18 p->children[i] = NULL;
19 }
20 p->words_amount = 0;
21 }
22
23 void insert_to_trie(char *buf, NODE *root) {
24 int len = strlen(buf);
25 int i;
26 NODE *p = root;
27 for (i = 0; i < len; ++i) {
28 int ch = buf[i] - 'a';
29 if (p->children[ch] == NULL) {
30 p->children[ch] = (NODE *)malloc(sizeof(NODE));
31 init_node(p->children[ch]);
32 }
33 p = p->children[ch];
34 }
35 p->words_amount++;
36 }
37
38 void destroy_trie(NODE *root) {
39 int i;
40 for (i = 0; i < MAX; ++i) {
41 if (root->children[i]) {
42 destroy_trie(root->children[i]);
43 }
44 }
45 free(root);
46 }
47
48 void bfs_for_next(NODE *root) {
49 int i;
50 if (!root) {
51 return;
52 }
53 root->next = NULL;
54 NODE *p = root;
55 std::queue<NODE *> q;
56 q.push(p);
57 while (!q.empty()) {
58 NODE *tmp = q.front();
59 q.pop();
60 for(i = 0; i < MAX; ++i) {
61 if (tmp->children[i]) {
62 if (tmp == root) {
63 tmp->children[i]->next = root;
64 } else {
65 NODE * pre = tmp->next;
66 while (pre != NULL) {
67 if (pre->children[i]) {
68 tmp->children[i]->next = pre->children[i];
69 break;
70 }
71 pre = pre->next;
72 }
73 if (pre == NULL) {
74 tmp->children[i]->next = root;
75 }
76 }
77 q.push(tmp->children[i]);
78 }
79 }
80 }
81 }
82
83 int search(char *buf, NODE *root) {
84 int i;
85 int count = 0;
86 int str_len = strlen(buf);
87 NODE *cur_node = root;
88 int cur_char;
89 for (i = 0; i < str_len; ++i) {
90 cur_char = buf[i] - 'a';
91 while (cur_node != root && !cur_node->children[cur_char]) {
92 cur_node = cur_node->next;
93 }
94 cur_node = cur_node->children[cur_char];
95 if (!cur_node) {
96 cur_node = root;
97 }
98 NODE *tmp = cur_node;
99 while (tmp != root && tmp->words_amount > 0) {
100 count += tmp->words_amount;
101 tmp->words_amount = 0;
102 tmp = tmp->next;
103 }
104 }
105 return count;
106 }
107
108 int main() {
109 int cases;
110 int n;
111 int i;
112 char *buf = (char *)malloc(sizeof(char) * 1000005);
113 scanf("%d", &cases);
114 while (cases--) {
115 scanf("%d", &n);
116 NODE *root = (NODE *)malloc(sizeof(NODE));
117 init_node(root);
118 for (i = 0; i < n; ++i) {
119 scanf("%s", buf);
120 insert_to_trie(buf, root);
121 }
122 scanf("%s", buf);
123 bfs_for_next(root);
124 printf("%d\n", search(buf, root));
125 destroy_trie(root);
126 }
127
128 return 0;
129 }
这里构造ac自动机的时候，每个节点都用malloc在堆中分配，当然也可以写成数组形式，效率应该会高一些，但是可扩展性就不够了
posted on 2012-09-12 15:46
myjfm 阅读(854)
评论(0) 编辑 收藏 引用 所属分类:
算法基础