【常用经典算法总结系列一】AC自动机

以你之姓@ 2022-07-14 04:24 101阅读 0赞

我要检查一篇文章中是否有某些敏感词，这其实就是多模式匹配的问题。

当然你也可以用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树还是很容易的。

![2012120214395327.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”节点，好，原理其实就是这样。（看看你的想法是不是跟图一样）

![2012120215091478.png][]

针对图中红线的”h，e“这两个节点，我们想起了什么呢？对”her“中的”e“来说，e到root距离的n个字符恰好与”she“中的e向上的n

个字符相等，我也非常类似于kmp中next函数，当字符失配时，next数组中记录着下一次匹配时模式串的起始位置。

![复制代码][copycode.gif]

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             /// 插入记录时的编号id
    29             /// </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

![复制代码][copycode.gif]

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

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

![复制代码][copycode.gif]

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                     //如果当前是根节点，则根节点的失败指针指向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         }

![复制代码][copycode.gif]

3：模式匹配

所有字符在匹配完后都必须要走failnode节点来结束自己的旅途,相当于一个回旋，这样做的目的防止包含节点被忽略掉。

比如：我匹配到了"she"，必然会匹配到该字符串的后缀”he"，要想在程序中匹配到，则必须节点要走失败指针来结束自己的旅途。

![2012120215443234.png][]

从上图中我们可以清楚的看到“she”的匹配到字符"e"后，从failnode指针撤退，在撤退途中将其后缀字符“e”收入囊肿，这也就是

为什么像kmp中的next函数。

![复制代码][copycode.gif]

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         }

![复制代码][copycode.gif]

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

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

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         #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 }

![复制代码][copycode.gif]

> ## 欢迎关注公众号： ##
> 
> # ![70][] #

[2012120214395327.png]: /images/20220714/11824f9935434ccfa15ccc5128a72233.png
[2012120215091478.png]: /images/20220714/907f59c132bd4730968b0237b7dfdc63.png
[copycode.gif]: /images/20220714/f8f50f96ad8a4389979d0edcd0ce68cb.png
[2012120215443234.png]: /images/20220714/4ebcb7f4c63a4bfd920e919a31b1b00f.png
[ExpandedBlockStart.gif]: /images/20220714/9ea0a49eb1394c27b1ba7311910d68d7.png
[70]: /images/20220714/85b423d4ba2f46bd8dced80a40661eb4.png