上一篇我們説了單模式匹配演算法 KMP，現在我們有需求了，我要檢查一篇文章中是否有某些敏感詞，這其實就是多模式匹配的問題。
當然你也可以用 KMP 演算法求出，那麼它的時間複雜度為 O(c*(m+n))，c：為模式串的個數。 m：為模式串的長度,n: 為正文的長度，那
麼這個複雜度就不再是線性了，我們學演算法就是希望能把要解決的問題優化到極致，這不，AC 自動機就派上用場了。
其實 AC 自動機就是 Trie 樹的一個活用，活用點就是灌輸了 kmp 的思想，從而再次把時間複雜度優化到線性的 O(N)，剛好我前面的文
章已經説過了 Trie 樹和 KMP，這裏還是預設大家都懂。
一：構建 AC 自動機
同樣我也用網上的經典例子，現有 say she shr he her 這樣 5 個模式串，主串為 yasherhs，我要做的就是哪些模式串在主串中出現過？
1: 構建 trie 樹
如果看過我前面的文章，構建 trie 樹還是很容易的。

2：失敗指標
構建失敗指標是 AC 自動機的核心所在，玩轉了它也就玩轉了 AC 自動機，失敗指標非常類似於 KMP 中的 next 陣列，也就是説，
當我的主串在 trie 樹中進行匹配的時候，如果當前節點不能再繼續進行匹配，那麼我們就會走到當前節點的 failNode 節點繼續進行
匹配，構建 failnode 節點也是很流程化的。
①：root 節點的子節點的 failnode 都是指向 root 。
②：當走到在 “she” 中的”h“節點時，我們給它的 failnode 設定什麼呢？此時就要走該節點（h) 的父節點 (s) 的失敗指標，一直回溯直
到找到某個節點的孩子節點也是當初節點同樣的字元 (h)，沒有找到的話，其失敗指標就指向 root 。
比如：h 節點的父節點為 s，s 的 failnode 節點為 root，走到 root 後繼續尋找子節點為 h 的節點，恰好我們找到了，（假如還是沒
有找到，則繼續走該節點的 failnode，嘿嘿，是不是很像一種回溯查詢），此時就將 ”she” 中的 “h” 節點的 fainode” 指向
“her” 中的 “h” 節點，好，原理其實就是這樣。（看看你的想法是不是跟圖一樣）

針對圖中紅線的”h，e“這兩個節點，我們想起了什麼呢？對”her“中的”e“來説，e 到 root 距離的 n 個字元恰好與”she“中的 e 向上的 n
個字元相等，我也非常類似於 kmp 中 next 函式，當字元失配時，next 陣列中記錄著下一次匹配時模式串的起始位置。

1 #region Trie 樹節點
2 ///

3 /// Trie 樹節點
4 ///

5 public class TrieNode
6 {
7 ///

8 /// 26 個字元，也就是 26 叉樹
9 ///

10 public TrieNode[] childNodes;
11
12 ///

13 /// 詞頻統計
14 ///

15 public int freq;
16
17 ///

18 /// 記錄該節點的字元
19 ///

20 public char nodeChar;
21
22 ///

23 /// 失敗指標
24 ///

25 public TrieNode faliNode;
26
27 ///

28 /// 插入記錄時的編號 id
29 ///

30 public HashSet hashSet = new HashSet();
31
32 ///

33 /// 初始化
34 ///

35 public TrieNode()
36 {
37 childNodes = new TrieNode[26];
38 freq = 0;
39 }
40 }
41 #endregion

剛才我也説到了 parent 和 current 兩個節點，在給 trie 中的節點賦 failnode 的時候，如果採用深度優先的話還是很麻煩的，因為我要實時
記錄當前節點的父節點，相信寫過樹的朋友都清楚，除了深搜，我們還有廣搜。

1 ///

2 /// 構建失敗指標 (這裏我們採用 BFS 的做法)
3 ///

4 /// 5 public void BuildFailNodeBFS(ref TrieNode root)
6 {
7 //根節點入隊
8 queue.Enqueue(root);
9
10 while (queue.Count != 0)
11 {
12 //出隊
13 var temp = queue.Dequeue();
14
15 //失敗節點
16 TrieNode failNode = null;
17
18 //26 叉樹
19 for (int i = 0; i < 26; i++) 20 { 21 //程式碼技巧：用 BFS 方式，從當前節點找其孩子節點，此時孩子節點 22 // 的父親正是當前節點，（避免了 parent 節點的存在） 23 if (temp.childNodes[i] == null) 24 continue; 25 26 //如果當前是根節點，則根節點的失敗指標指向 root 27 if (temp == root) 28 { 29 temp.childNodes[i].faliNode = root; 30 } 31 else 32 { 33 //獲取出隊節點的失敗指標 34 failNode = temp.faliNode; 35 36 //沿著它父節點的失敗指標走，一直要找到一個節點，直到它的兒子也包含該節點。 37 while (failNode != null) 38 { 39 //如果不為空，則在父親失敗節點中往子節點中深入。 40 if (failNode.childNodes[i] != null) 41 { 42 temp.childNodes[i].faliNode = failNode.childNodes[i]; 43 break; 44 } 45 //如果無法深入子節點，則退回到父親失敗節點並向 root 節點往根部延伸，直到 null 46 //（一個回溯再深入的過程，非常有意思） 47 failNode = failNode.faliNode; 48 } 49 50 //等於 null 的話，指向 root 節點 51 if (failNode == null) 52 temp.childNodes[i].faliNode = root; 53 } 54 queue.Enqueue(temp.childNodes[i]); 55 } 56 } 57 } 3：模式匹配 所有字元在匹配完後都必須要走 failnode 節點來結束自己的旅途, 相當於一個迴旋，這樣做的目的防止包含節點被忽略掉。 比如：我匹配到了”she”，必然會匹配到該字串的字尾”he”，要想在程式中匹配到，則必須節點要走失敗指標來結束自己的旅途。 從上圖中我們可以清楚的看到 “she” 的匹配到字元”e” 後，從 failnode 指標撤退，在撤退途中將其字尾字元 “e” 收入囊腫，這也就是 為什麼像 kmp 中的 next 函式。 1 ///

2 /// 根據指定的主串，檢索是否存在模式串
3 ///

4 /// 5 /// 6 ///
7 public void SearchAC(ref TrieNode root, string s, ref HashSet hashSet)
8 {
9 int freq = 0;
10
11 TrieNode head = root;
12
13 foreach (var c in s)
14 {
15 //計算位置
16 int index = c – ‘a’;
17
18 //如果當前匹配的字元在 trie 樹中無子節點並且不是 root，則要走失敗指標
19 //回溯的去找它的當前節點的子節點
20 while ((head.childNodes[index] == null) && (head != root))
21 head = head.faliNode;
22
23 //獲取該叉樹
24 head = head.childNodes[index];
25
26 //如果為空，直接給 root, 表示該字元已經走完畢了
27 if (head == null)
28 head = root;
29
30 var temp = head;
31
32 //在 trie 樹中匹配到了字元，標記當前節點為已訪問，並繼續尋找該節點的失敗節點。
33 //直到 root 結束，相當於走了一個迴旋。 (注意：最後我們會出現一個 freq=-1 的失敗指標鏈)
34 while (temp != root && temp.freq != -1)
35 {
36 freq += temp.freq;
37
38 //將找到的 id 追加到集合中
39 foreach (var item in temp.hashSet)
40 hashSet.Add(item);
41
42 temp.freq = -1;
43
44 temp = temp.faliNode;
45 }
46 }
47 }

好了，到現在為止，我想大家也比較清楚了，最後上一個總的執行程式碼：

1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Diagnostics;
6 using System.Threading;
7 using System.IO;
8
9 namespace ConsoleApplication2
10 {
11 public class Program
12 {
13 public static void Main()
14 {
15 Trie trie = new Trie();
16
17 trie.AddTrieNode(“say”, 1);
18 trie.AddTrieNode(“she”, 2);
19 trie.AddTrieNode(“shr”, 3);
20 trie.AddTrieNode(“her”, 4);
21 trie.AddTrieNode(“he”, 5);
22
23 trie.BuildFailNodeBFS();
24
25 string s = “yasherhs”;
26
27 var hashSet = trie.SearchAC(s);
28
29 Console.WriteLine(“ 在主串 {0} 中存在模式串的編號為:{1}”, s, string.Join(“,”, hashSet));
30
31 Console.Read();
32 }
33 }
34
35 public class Trie
36 {
37 public TrieNode trieNode = new TrieNode();
38
39 ///

40 /// 用光搜的方法來構建失敗指標
41 ///

42 public Queue queue = new Queue();
43
44 #region Trie 樹節點
45 ///

46 /// Trie 樹節點
47 ///

48 public class TrieNode
49 {
50 ///

51 /// 26 個字元，也就是 26 叉樹
52 ///

53 public TrieNode[] childNodes;
54
55 ///

56 /// 詞頻統計
57 ///

58 public int freq;
59
60 ///

61 /// 記錄該節點的字元
62 ///

63 public char nodeChar;
64
65 ///

66 /// 失敗指標
67 ///

68 public TrieNode faliNode;
69
70 ///

71 /// 插入記錄時的編號 id
72 ///

73 public HashSet hashSet = new HashSet();
74
75 ///

76 /// 初始化
77 ///

78 public TrieNode()
79 {
80 childNodes = new TrieNode[26];
81 freq = 0;
82 }
83 }
84 #endregion
85
86 #region 插入操作
87 ///

88 /// 插入操作
89 ///

90 /// 91 /// 92 public void AddTrieNode(string word, int id)
93 {
94 AddTrieNode(ref trieNode, word, id);
95 }
96
97 ///

98 /// 插入操作
99 ///

100 /// 101 /// 102 public void AddTrieNode(ref TrieNode root, string word, int id)
103 {
104 if (word.Length == 0)
105 return;
106
107 //求字元地址，方便將該字元放入到 26 叉樹中的哪一叉中
108 int k = word[0] – ‘a’;
109
110 //如果該叉樹為空，則初始化
111 if (root.childNodes[k] == null)
112 {
113 root.childNodes[k] = new TrieNode();
114
115 //記錄下字元
116 root.childNodes[k].nodeChar = word[0];
117 }
118
119 var nextWord = word.Substring(1);
120
121 //説明是最後一個字元，統計該詞出現的次數
122 if (nextWord.Length == 0)
123 {
124 root.childNodes[k].freq++;
125 root.childNodes[k].hashSet.Add(id);
126 }
127
128 AddTrieNode(ref root.childNodes[k], nextWord, id);
129 }
130 #endregion
131
132 #region 構建失敗指標
133 ///

134 /// 構建失敗指標 (這裏我們採用 BFS 的做法)
135 ///

136 public void BuildFailNodeBFS()
137 {
138 BuildFailNodeBFS(ref trieNode);
139 }
140
141 ///

142 /// 構建失敗指標 (這裏我們採用 BFS 的做法)
143 ///

144 /// 145 public void BuildFailNodeBFS(ref TrieNode root)
146 {
147 //根節點入隊
148 queue.Enqueue(root);
149
150 while (queue.Count != 0)
151 {
152 //出隊
153 var temp = queue.Dequeue();
154
155 //失敗節點
156 TrieNode failNode = null;
157
158 //26 叉樹
159 for (int i = 0; i < 26; i++) 160 { 161 //程式碼技巧：用 BFS 方式，從當前節點找其孩子節點，此時孩子節點 162 // 的父親正是當前節點，（避免了 parent 節點的存在） 163 if (temp.childNodes[i] == null) 164 continue; 165 166 //如果當前是根節點，則根節點的失敗指標指向 root 167 if (temp == root) 168 { 169 temp.childNodes[i].faliNode = root; 170 } 171 else 172 { 173 //獲取出隊節點的失敗指標 174 failNode = temp.faliNode; 175 176 //沿著它父節點的失敗指標走，一直要找到一個節點，直到它的兒子也包含該節點。 177 while (failNode != null) 178 { 179 //如果不為空，則在父親失敗節點中往子節點中深入。 180 if (failNode.childNodes[i] != null) 181 { 182 temp.childNodes[i].faliNode = failNode.childNodes[i]; 183 break; 184 } 185 //如果無法深入子節點，則退回到父親失敗節點並向 root 節點往根部延伸，直到 null 186 //（一個回溯再深入的過程，非常有意思） 187 failNode = failNode.faliNode; 188 } 189 190 //等於 null 的話，指向 root 節點 191 if (failNode == null) 192 temp.childNodes[i].faliNode = root; 193 } 194 queue.Enqueue(temp.childNodes[i]); 195 } 196 } 197 } 198 #endregion 199 200 #region 檢索操作 201 ///

202 /// 根據指定的主串，檢索是否存在模式串
203 ///

204 /// 205 ///
206 public HashSet SearchAC(string s)
207 {
208 HashSet hash = new HashSet();
209
210 SearchAC(ref trieNode, s, ref hash);
211
212 return hash;
213 }
214
215 ///

216 /// 根據指定的主串，檢索是否存在模式串
217 ///

218 /// 219 /// 220 ///
221 public void SearchAC(ref TrieNode root, string s, ref HashSet hashSet)
222 {
223 int freq = 0;
224
225 TrieNode head = root;
226
227 foreach (var c in s)
228 {
229 //計算位置
230 int index = c – ‘a’;
231
232 //如果當前匹配的字元在 trie 樹中無子節點並且不是 root，則要走失敗指標
233 //回溯的去找它的當前節點的子節點
234 while ((head.childNodes[index] == null) && (head != root))
235 head = head.faliNode;
236
237 //獲取該叉樹
238 head = head.childNodes[index];
239
240 //如果為空，直接給 root, 表示該字元已經走完畢了
241 if (head == null)
242 head = root;
243
244 var temp = head;
245
246 //在 trie 樹中匹配到了字元，標記當前節點為已訪問，並繼續尋找該節點的失敗節點。
247 //直到 root 結束，相當於走了一個迴旋。 (注意：最後我們會出現一個 freq=-1 的失敗指標鏈)
248 while (temp != root && temp.freq != -1)
249 {
250 freq += temp.freq;
251
252 //將找到的 id 追加到集合中
253 foreach (var item in temp.hashSet)
254 hashSet.Add(item);
255
256 temp.freq = -1;
257
258 temp = temp.faliNode;
259 }
260 }
261 }
262 #endregion
263 }
264 }