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 閱讀(884)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎