首页 > 代码库 > 经典算法题每日演练——第八题 AC自动机

经典算法题每日演练——第八题 AC自动机

原文:经典算法题每日演练——第八题 AC自动机

 

     上一篇我们说了单模式匹配算法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         /// <summary> 3         /// Trie树节点 4         /// </summary> 5         public class TrieNode 6         { 7             /// <summary> 8             /// 26个字符,也就是26叉树 9             /// </summary>10             public TrieNode[] childNodes;11 12             /// <summary>13             /// 词频统计14             /// </summary>15             public int freq;16 17             /// <summary>18             /// 记录该节点的字符19             /// </summary>20             public char nodeChar;21 22             /// <summary>23             /// 失败指针24             /// </summary>25             public TrieNode faliNode;26 27             /// <summary>28             /// 插入记录时的编号id29             /// </summary>30             public HashSet<int> hashSet = new HashSet<int>();31 32             /// <summary>33             /// 初始化34             /// </summary>35             public TrieNode()36             {37                 childNodes = new TrieNode[26];38                 freq = 0;39             }40         }41         #endregion

刚才我也说到了parent和current两个节点,在给trie中的节点赋failnode的时候,如果采用深度优先的话还是很麻烦的,因为我要实时

记录当前节点的父节点,相信写过树的朋友都清楚,除了深搜,我们还有广搜。

 1  /// <summary> 2         /// 构建失败指针(这里我们采用BFS的做法) 3         /// </summary> 4         /// <param name="root"></param> 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                     //如果当前是根节点,则根节点的失败指针指向root27                     if (temp == root)28                     {29                         temp.childNodes[i].faliNode = root;30                     }31                     else32                     {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节点往根部延伸,直到null46                             //(一个回溯再深入的过程,非常有意思)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         /// <summary> 2         /// 根据指定的主串,检索是否存在模式串 3         /// </summary> 4         /// <param name="root"></param> 5         /// <param name="s"></param> 6         /// <returns></returns> 7         public void SearchAC(ref TrieNode root, string s, ref HashSet<int> 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         }

好了,到现在为止,我想大家也比较清楚了,最后上一个总的运行代码:

技术分享View Code
  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         /// <summary> 40         /// 用光搜的方法来构建失败指针 41         /// </summary> 42         public Queue<TrieNode> queue = new Queue<TrieNode>(); 43  44         #region Trie树节点 45         /// <summary> 46         /// Trie树节点 47         /// </summary> 48         public class TrieNode 49         { 50             /// <summary> 51             /// 26个字符,也就是26叉树 52             /// </summary> 53             public TrieNode[] childNodes; 54  55             /// <summary> 56             /// 词频统计 57             /// </summary> 58             public int freq; 59  60             /// <summary> 61             /// 记录该节点的字符 62             /// </summary> 63             public char nodeChar; 64  65             /// <summary> 66             /// 失败指针 67             /// </summary> 68             public TrieNode faliNode; 69  70             /// <summary> 71             /// 插入记录时的编号id 72             /// </summary> 73             public HashSet<int> hashSet = new HashSet<int>(); 74  75             /// <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         #endregion131 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                     //如果当前是根节点,则根节点的失败指针指向root167                     if (temp == root)168                     {169                         temp.childNodes[i].faliNode = root;170                     }171                     else172                     {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节点往根部延伸,直到null186                             //(一个回溯再深入的过程,非常有意思)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         #endregion199 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         #endregion263     }264 }

 

经典算法题每日演练——第八题 AC自动机