基于C#实现AC自动机算法

我要检查一篇文章中是否有某些敏感词，这其实就是多模式匹配的问题。当然你也可以用 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 树还是很容易的。
image.png

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”节点，好，原理其实就是这样。（看看你的想法是不是跟图一样）
image.png
针对图中红线的”h，e“这两个节点，我们想起了什么呢？对”her“中的”e“来说，e 到 root 距离的 n 个字符恰好与”she“中的 e 向上的 n 个字符相等，我也非常类似于 kmp 中 next 函数，当字符失配时，next 数组中记录着下一次匹配时模式串的起始位置。

 #region Trie树节点
 /// <summary>
 /// Trie树节点
 /// </summary>
 public class TrieNode
 {
     /// <summary>
     /// 26个字符，也就是26叉树
     /// </summary>
     public TrieNode[] childNodes;

     /// <summary>
     /// 词频统计
     /// </summary>
     public int freq;

     /// <summary>
     /// 记录该节点的字符
     /// </summary>
     public char nodeChar;

     /// <summary>
     /// 失败指针
     /// </summary>
     public TrieNode faliNode;

     /// <summary>
     /// 插入记录时的编号id
     /// </summary>
     public HashSet<int> hashSet = new HashSet<int>();

     /// <summary>
     /// 初始化
     /// </summary>
     public TrieNode()
     {
         childNodes = new TrieNode[26];
         freq = 0;
     }
 }
 #endregion

刚才说到了 parent 和 current 两个节点，在给 trie 中的节点赋 failnode 的时候，如果采用深度优先的话还是很麻烦的，因为我要实时记录当前节点的父节点，相信写过树的朋友都清楚，除了深搜，我们还有广搜。

  /// <summary>
 /// 构建失败指针(这里我们采用BFS的做法)
 /// </summary>
 /// <param name="root"></param>
 public 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;

             //如果当前是根节点，则根节点的失败指针指向root
             if (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"，要想在程序中匹配到，则必须节点要走失败指针来结束自己的旅途。
image.png
从上图中我们可以清楚的看到“she”的匹配到字符"e"后，从 failnode 指针撤退，在撤退途中将其后缀字符“e”收入囊肿，这也就是为什么像 kmp 中的 next 函数。

/// <summary>
/// 根据指定的主串，检索是否存在模式串
/// </summary>
/// <param name="root"></param>
/// <param name="s"></param>
/// <returns></returns>
public void SearchAC(ref TrieNode root, string s, ref HashSet<int> 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>
          /// 用光搜的方法来构建失败指针
          /// </summary>
          public Queue<TrieNode> queue = new Queue<TrieNode>();
  
          #region Trie树节点
          /// <summary>
          /// Trie树节点
          /// </summary>
          public class TrieNode
          {
              /// <summary>
              /// 26个字符，也就是26叉树
              /// </summary>
              public TrieNode[] childNodes;
  
              /// <summary>
              /// 词频统计
              /// </summary>
              public int freq;
  
              /// <summary>
              /// 记录该节点的字符
              /// </summary>
              public char nodeChar;
  
              /// <summary>
              /// 失败指针
              /// </summary>
              public TrieNode faliNode;
  
              /// <summary>
              /// 插入记录时的编号id
              /// </summary>
              public HashSet<int> hashSet = new HashSet<int>();
  
              /// <summary>
 76             /// 初始化
 77             /// </summary>
 78             public TrieNode()
 79             {
 80                 childNodes = new TrieNode[26];
 81                 freq = 0;
 82             }
 83         }
 84         #endregion
 85 
 86         #region 插入操作
 87         /// <summary>
 88         /// 插入操作
 89         /// </summary>
 90         /// <param name="word"></param>
 91         /// <param name="id"></param>
 92         public void AddTrieNode(string word, int id)
 93         {
 94             AddTrieNode(ref trieNode, word, id);
 95         }
 96 
 97         /// <summary>
 98         /// 插入操作
 99         /// </summary>
100         /// <param name="root"></param>
101         /// <param name="s"></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 name="root"></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 name="s"></param>
205         /// <returns></returns>
206         public HashSet<int> SearchAC(string s)
207         {
208             HashSet<int> hash = new HashSet<int>();
209 
210             SearchAC(ref trieNode, s, ref hash);
211 
212             return hash;
213         }
214 
215         /// <summary>
216         /// 根据指定的主串，检索是否存在模式串
217         /// </summary>
218         /// <param name="root"></param>
219         /// <param name="s"></param>
220         /// <returns></returns>
221         public void SearchAC(ref TrieNode root, string s, ref HashSet<int> 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 }

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/174230.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Macs Fan Control Pro：掌握您的Mac风扇，提升散热效率

Macs Fan Control Pro：掌握您的Mac风扇，提升散热效率

在Mac的世界里&#xff0c;每一个细节都显得格外重要。而其中&#xff0c;风扇的控制与调节则显得尤为重要。然而&#xff0c;原生的Mac系统并不提供直观的风扇控制工具&#xff0c;这使得许多Mac用户在处理高负荷任务时&#xff0c;风扇无法有效地进行散热&#xff0c;导致机器…
阅读更多...
TensorFlow实战教程（十八）-Keras搭建卷积神经网络及CNN原理详解

TensorFlow实战教程（十八）-Keras搭建卷积神经网络及CNN原理详解

从本专栏开始，作者正式研究Python深度学习、神经网络及人工智能相关知识。前一篇文章详细讲解了Keras实现分类学习，以MNIST数字图片为例进行讲解。本篇文章详细讲解了卷积神经网络CNN原理，并通过Keras编写CNN实现了MNIST分类学习案例。基础性文章，希望对您有所帮助！ 一…
阅读更多...
体感互动游戏VR游戏AR体感游戏软件开发

体感互动游戏VR游戏AR体感游戏软件开发

随着科技的不断发展&#xff0c;体感互动游戏正逐渐成为游戏行业的一个重要趋势。这类游戏通过利用传感器、摄像头和运动控制器等技术&#xff0c;使玩家能够通过身体动作与游戏进行实时互动&#xff0c;极大地提升了娱乐体验。 1. 游戏设计与互动元素 体感互动游戏的核心在于…
阅读更多...
使用kafka_exporter监控Kafka

使用kafka_exporter监控Kafka

prometheus 监控 kafka 常见的有两种开源方案，一种是传统的部署 exporter 的方式，一种是通过 jmx 配置监控， 项目地址： kafka_exporter：https://github.com/danielqsj/kafka_exporterjmx_exporter：https://github.com/prometheus/jmx_exporter本文将采用kafka_exporter方…
阅读更多...
使用Navicat将SQL server数据库导入mysql数据库

使用Navicat将SQL server数据库导入mysql数据库

使用Navicat将SQL server数据库导入mysql数据库 1、使用Navicat Premium打开MySql数据库&#xff0c;然后新建一个数据库名&#xff08;该数据库名称为需要从SqlServer数据库导过来的名称&#xff0c;mysql只有小写&#xff0c;不影响&#xff09; 比如需要将SqlServer数据库…
阅读更多...
NGINX缓存详解之服务端缓存

NGINX缓存详解之服务端缓存

服务端缓存 proxy cache属于服务端缓存，主要实现 nginx 服务器对客户端数据请求的快速响应。 nginx 服务器在接收到被代理服务器的响应数据之后，一方面将数据传递给客户端，另一方面根据proxy cache的配置将这些数据缓存到本地硬盘上。 当客户端再次访问相同的数据时，nginx…
阅读更多...
谈谈你对mvc和mvvm的理解

谈谈你对mvc和mvvm的理解

MVC和MVVM是软件开发中两种常见的架构模式&#xff0c;各自有不同的优缺点。 MVC&#xff08;Model-View-Controller&#xff09;是一种经典的架构模式&#xff0c;将应用程序分为三个部分&#xff1a;模型&#xff08;Model&#xff09;、视图&#xff08;View&#xff09;和…
阅读更多...
中国城镇化时空分异及影响因素数据集（2010-2020）

中国城镇化时空分异及影响因素数据集（2010-2020）

基于《中国统计年鉴》、各省份统计年鉴及EPS全球统计数据库等相关统计数据&#xff0c;从人居生活、人文环境、人城关系等维度界定了城镇化内涵框架与指标体系&#xff0c;利用改进的熵值法计算综合评价指数&#xff0c;并运用泰尔指数、方差分解及地理探测器等方法&#xff0c…
阅读更多...
ventoy安装操作系统

ventoy安装操作系统

下载ventoy https://github.com/ventoy/Ventoy/releases/download/v1.0.96/ventoy-1.0.96-windows.zip 解压后执行 Ventoy2Disk 2、安装后将ISO放入U盘大的分区&#xff0c;通过U盘启动就可以识别到ISO镜像开始装系统
阅读更多...
2021秋招-总目录

2021秋招-总目录

2021秋招-目录 知识点总结 预训练语言模型: Bert家族 1.1 BERT、attention、transformer理解部分 B站讲解–强烈推荐可视化推倒结合代码理解代码部分常见面试考点以及问题: word2vec 、 fasttext 、elmo;BN 、LN、CN、WNNLP中的loss与评价总结 4.1 loss_function&#xff1…
阅读更多...
【Java】异常处理及其语法、抛出异常、自定义异常（完结）

【Java】异常处理及其语法、抛出异常、自定义异常（完结）

&#x1f33a;个人主页&#xff1a;Dawn黎明开始 &#x1f380;系列专栏&#xff1a;Java ⭐每日一句&#xff1a;道阻且长&#xff0c;行则将至 &#x1f4e2;欢迎大家&#xff1a;关注&#x1f50d;点赞&#x1f44d;评论&#x1f4dd;收藏⭐️ 文章目录 一.&#x1f510;异…
阅读更多...
centos7卸载mongodb数据重新安装时无法安装的问题

centos7卸载mongodb数据重新安装时无法安装的问题

如果卸载不干净直接用 sudo find / -name mongo 查询所有关于mongo的文件&#xff0c;然后一个个去删除。 当然最好的办法还是去看日志信息。 直接去查看日志信息 sudo cat /var/log/mongodb/mongod.log 根据提示信息说这个没有权限操作 直接删除即可&#xff0c;都是之前…
阅读更多...
【Web】Ctfshow XSS刷题记录

【Web】Ctfshow XSS刷题记录

目录 反射型XSS ①web316 ②web317-319 ③web320-322 ④web323-326 存储型XSS ①web327 ②web328 ③web329 ④web330 ⑤web331 ⑥web332-333 反射型XSS ①web316 直接输入<script>alert(1)</script>,能弹窗。xss题目一般会有个bot&#xff0c;可以触…
阅读更多...
django+drf+vue 简单系统搭建 （4） 用户权限

django+drf+vue 简单系统搭建 （4） 用户权限

权限控制是web中的重要组成部分。与以往的博客系统不同&#xff0c;本次工具页面仅支持注册用户。 每个注册用户都能访问到工具页面&#xff0c;并且提交自己的task来选择具体的工具来处理自己提交的文件。每个注册用户都只能访问到自己提交的task&#xff0c;而管理员则可以查…
阅读更多...
Android DatePicker(日期选择器)、TimePicker(时间选择器)、CalendarView(日历视图)- 简单应用

Android DatePicker(日期选择器)、TimePicker(时间选择器)、CalendarView(日历视图)- 简单应用

示意图&#xff1a; layout布局文件&#xff1a;xml <?xml version"1.0" encoding"utf-8"?> <ScrollView xmlns:android"http://schemas.android.com/apk/res/android"xmlns:app"http://schemas.android.com/apk/res-auto"…
阅读更多...
vue中原生H5拖拽排序_拖拽图片也是同样的道理

vue中原生H5拖拽排序_拖拽图片也是同样的道理

原文地址【vue中原生H5拖拽排序_拖拽图片也是同样的道理】 H5有基于拖拽的事件机制&#xff0c;如果你还不熟悉&#xff0c;请看我之前的文章【拖拽上传】中有介绍。 原生拖拽API实现 由于比较简单直接上代码了&#xff1a; <!DOCTYPE html> <html lang"en&qu…
阅读更多...
https和http的区别和优势

https和http的区别和优势

大家好&#xff0c;我是咕噜-凯撒&#xff0c;HTTP&#xff08;超文本传输协议&#xff09;和HTTPS&#xff08;安全超文本传输协议&#xff09;是用于在网络上传输数据的协议&#xff0c;HTTPS相比HTTP在数据传输过程中更加安全可靠&#xff0c;适合对数据安全性要求较高的场景…
阅读更多...
【冒泡排序设计】

【冒泡排序设计】

【冒泡排序设计】 思路代码结果 思路 冒泡排序这个算法&#xff0c;对于我这样的初学者来说&#xff0c;也不是很简单&#xff01;&#xff01;&#xff01;&#xff08;没有想象的那么简单&#xff09;&#xff01;  它的核心思想是&#xff1a;两两相邻的元素进行比较&#…
阅读更多...
Android HAL学习 及 与BSP的区别

Android HAL学习 及 与BSP的区别

Android HAL学习 及 与BSP的区别 参考链接&#xff1a; 1、https://www.cnblogs.com/looner/articles/11579335.html 2、https://blog.csdn.net/leesan0802/article/details/124087630 3、https://zhuanlan.zhihu.com/p/336531442 在HAL的学习之前&#xff0c;我们来先了解…
阅读更多...
02-微服务的拆分规则和基于RestTemplate的远程调用

02-微服务的拆分规则和基于RestTemplate的远程调用

微服务的拆分与远程调用 创建父工程 任何分布式架构都离不开服务的拆分, 微服务也是一样 , 微服务的拆分遵守三个原则 微服务需要根据业务模块拆分,不同微服务不要重复开发相同业务每个微服务都有自己独立的数据库, 不要直接访问其他微服务的数据库微服务可以将自己的业务暴…
阅读更多...
最新文章

Copyright @ 2022~2023