深圳网站建设制作品牌公司,从网站验证码谈用户体验,WordPress资讯站点源码,360建设网站免费我要检查一篇文章中是否有某些敏感词#xff0c;这其实就是多模式匹配的问题。当然你也可以用 KMP 算法求出#xff0c;那么它的时间复杂度为 O(c*(mn))#xff0c;c#xff1a;为模式串的个数。m#xff1a;为模式串的长度,n:为正文的长度#xff0c;那么这个复杂度就不…我要检查一篇文章中是否有某些敏感词这其实就是多模式匹配的问题。当然你也可以用 KMP 算法求出那么它的时间复杂度为 O(c*(mn))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 节点的父节点为 ss 的 failnode 节点为 root走到 root 后继续寻找子节点为 h 的节点恰好我们找到了假如还是没有找到则继续走该节点的 failnode嘿嘿是不是很像一种回溯查找此时就将 ”she中的“h”节点的 fainode指向her中的“h”节点好原理其实就是这样。看看你的想法是不是跟图一样 针对图中红线的”he“这两个节点我们想起了什么呢对”her“中的”e“来说e 到 root 距离的 n 个字符恰好与”she“中的 e 向上的 n 个字符相等我也非常类似于 kmp 中 next 函数当字符失配时next 数组中记录着下一次匹配时模式串的起始位置。 #region Trie树节点/// summary/// Trie树节点/// /summarypublic class TrieNode{/// summary/// 26个字符也就是26叉树/// /summarypublic TrieNode[] childNodes;/// summary/// 词频统计/// /summarypublic int freq;/// summary/// 记录该节点的字符/// /summarypublic char nodeChar;/// summary/// 失败指针/// /summarypublic TrieNode faliNode;/// summary/// 插入记录时的编号id/// /summarypublic HashSetint hashSet new HashSetint();/// summary/// 初始化/// /summarypublic TrieNode(){childNodes new TrieNode[26];freq 0;}}#endregion刚才说到了 parent 和 current 两个节点在给 trie 中的节点赋 failnode 的时候如果采用深度优先的话还是很麻烦的因为我要实时记录当前节点的父节点相信写过树的朋友都清楚除了深搜我们还有广搜。 /// summary/// 构建失败指针(这里我们采用BFS的做法)/// /summary/// param nameroot/parampublic void BuildFailNodeBFS(ref TrieNode root){//根节点入队queue.Enqueue(root);while (queue.Count ! 0){//出队var temp queue.Dequeue();//失败节点TrieNode failNode null;//26叉树for (int i 0; i 26; i){//代码技巧用BFS方式从当前节点找其孩子节点此时孩子节点// 的父亲正是当前节点避免了parent节点的存在if (temp.childNodes[i] null)continue;//如果当前是根节点则根节点的失败指针指向rootif (temp root){temp.childNodes[i].faliNode root;}else{//获取出队节点的失败指针failNode temp.faliNode;//沿着它父节点的失败指针走一直要找到一个节点直到它的儿子也包含该节点。while (failNode ! null){//如果不为空则在父亲失败节点中往子节点中深入。if (failNode.childNodes[i] ! null){temp.childNodes[i].faliNode failNode.childNodes[i];break;}//如果无法深入子节点则退回到父亲失败节点并向root节点往根部延伸直到null//一个回溯再深入的过程非常有意思failNode failNode.faliNode;}//等于null的话指向root节点if (failNode null)temp.childNodes[i].faliNode root;}queue.Enqueue(temp.childNodes[i]);}}}3、模式匹配
所有字符在匹配完后都必须要走 failnode 节点来结束自己的旅途,相当于一个回旋这样做的目的防止包含节点被忽略掉。比如我匹配到了she必然会匹配到该字符串的后缀”he要想在程序中匹配到则必须节点要走失败指针来结束自己的旅途。 从上图中我们可以清楚的看到“she”的匹配到字符e后从 failnode 指针撤退在撤退途中将其后缀字符“e”收入囊肿这也就是为什么像 kmp 中的 next 函数。
/// summary
/// 根据指定的主串检索是否存在模式串
/// /summary
/// param nameroot/param
/// param names/param
/// returns/returns
public void SearchAC(ref TrieNode root, string s, ref HashSetint hashSet)
{int freq 0;TrieNode head root;foreach (var c in s){//计算位置int index c - a;//如果当前匹配的字符在trie树中无子节点并且不是root则要走失败指针//回溯的去找它的当前节点的子节点while ((head.childNodes[index] null) (head ! root))head head.faliNode;//获取该叉树head head.childNodes[index];//如果为空直接给root,表示该字符已经走完毕了if (head null)head root;var temp head;//在trie树中匹配到了字符标记当前节点为已访问并继续寻找该节点的失败节点。//直到root结束相当于走了一个回旋。(注意最后我们会出现一个freq-1的失败指针链)while (temp ! root temp.freq ! -1){freq temp.freq;//将找到的id追加到集合中foreach (var item in temp.hashSet)hashSet.Add(item);temp.freq -1;temp temp.faliNode;}}
}好了到现在为止我想大家也比较清楚了最后上一个总的运行代码 using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Diagnostics;using System.Threading;using System.IO;namespace ConsoleApplication2{public class Program{public static void Main(){Trie trie new Trie();trie.AddTrieNode(say, 1);trie.AddTrieNode(she, 2);trie.AddTrieNode(shr, 3);trie.AddTrieNode(her, 4);trie.AddTrieNode(he, 5);trie.BuildFailNodeBFS();string s yasherhs;var hashSet trie.SearchAC(s);Console.WriteLine(在主串{0}中存在模式串的编号为:{1}, s, string.Join(,, hashSet));Console.Read();}}public class Trie{public TrieNode trieNode new TrieNode();/// summary/// 用光搜的方法来构建失败指针/// /summarypublic QueueTrieNode queue new QueueTrieNode();#region Trie树节点/// summary/// Trie树节点/// /summarypublic class TrieNode{/// summary/// 26个字符也就是26叉树/// /summarypublic TrieNode[] childNodes;/// summary/// 词频统计/// /summarypublic int freq;/// summary/// 记录该节点的字符/// /summarypublic char nodeChar;/// summary/// 失败指针/// /summarypublic TrieNode faliNode;/// summary/// 插入记录时的编号id/// /summarypublic HashSetint hashSet new HashSetint();/// summary76 /// 初始化77 /// /summary78 public TrieNode()79 {80 childNodes new TrieNode[26];81 freq 0;82 }83 }84 #endregion85 86 #region 插入操作87 /// summary88 /// 插入操作89 /// /summary90 /// param nameword/param91 /// param nameid/param92 public void AddTrieNode(string word, int id)93 {94 AddTrieNode(ref trieNode, word, id);95 }96 97 /// summary98 /// 插入操作99 /// /summary
100 /// param nameroot/param
101 /// param names/param
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 /// summary
134 /// 构建失败指针(这里我们采用BFS的做法)
135 /// /summary
136 public void BuildFailNodeBFS()
137 {
138 BuildFailNodeBFS(ref trieNode);
139 }
140
141 /// summary
142 /// 构建失败指针(这里我们采用BFS的做法)
143 /// /summary
144 /// param nameroot/param
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 /// summary
202 /// 根据指定的主串检索是否存在模式串
203 /// /summary
204 /// param names/param
205 /// returns/returns
206 public HashSetint SearchAC(string s)
207 {
208 HashSetint hash new HashSetint();
209
210 SearchAC(ref trieNode, s, ref hash);
211
212 return hash;
213 }
214
215 /// summary
216 /// 根据指定的主串检索是否存在模式串
217 /// /summary
218 /// param nameroot/param
219 /// param names/param
220 /// returns/returns
221 public void SearchAC(ref TrieNode root, string s, ref HashSetint 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 }
