导语
由于学习AC自动机必须掌握Trie树和KMP算法（KMP算法可以移步：全网最通俗的KMP算法图解），因此本篇主要讲解Trie树和AC自动机。最终目标是掌握两种数据结构的特点并能够在项目中运用起来。以下为文章结构（阅读全文大约需要10分钟）：
Trie树
01简介
Tire树也叫字典树，是一种特殊的前缀树结构。它是哈希树的一种变种，专门为字符串处理设计的数据结构。典型的应用是用于统计和排序大量的字符串（不限于字符串）因此经常被搜索引擎用于文字词频统计。它的优点是：最大限度地减少无谓的字符串比较。Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
如图所示就是一棵Trie树，根节点不存字符，红色表示结束字符串，表示一个字符串的终止。
02特性
前缀树的3个基本性质：
1.根节点不包含字符，除根节点外每一个节点只包含一个字符。
2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3.每个节点的所有子节点包含的字符都不相同。
03核心思想
插入字符串：依次插入字符串apple、aply、cold、cool、cook
查询字符串：查询apple，存在该字符串
查询app，不存在该字符串
删除字符串cook:
删除cold:
04应用
1.字符串检索:事先将已知的一些字符串（字典）的有关信息保存到trie树里，查找另外一些未知字符串是否出现过或者出现频率。
2.字符串最长公共前缀:Trie树利用多个字符串的公共前缀来节省存储空间，反之，当我们把大量字符串存储到一棵trie树上时，我们可以快速得到某些字符串的公共前缀。
3.排序:Trie树是一棵多叉树，只要先遍历整棵树，输出相应的字符串便是按字典序排序的结果。
05python代码实现
AC自动机
01简介
AC自动机是最一种多模式匹配算法，它由贝尔实验室的两位研究人员Alfred V. Aho 和 Margaret J.Corasick 于1975年发明，几乎与KMP算法同时问世，至今仍然在模式匹配领域被广泛应用。例如：在一篇文章中，需要找到多个词汇所在的位置和出现频率。
其核心算法仍是寻找模式串内部规律，进行每次失配的高效跳转。这点和KMP算法一致，不同点在于,AC自动机寻找模式串的相同前缀。
AC自动机使用前缀树来存放所有模式串的前缀，通过失配指针来处理失配的跳转。AC自动机的构建，首先需要构建Trie树，其次需要添加失配指针（fail表），最后需要模式匹配。下图是用单词her、say、she、shr、he构成的AC自动机。
02核心思想
第一步：构建Trie树，前一章节已经讲过了如何构建Trie树。因此，直接得到下图：
构建fail表之前，我们需要明确，每个节点：父节点、子节点列表、fail节点、节点的值和是否是尾节点这几个属性组成：
第二步：构建fail表
fail表中保存了失配时的fail指针，fail指针就是当前位置失配以后能够跳转继续进行匹配的字符位置，达到匹配过程中不需要回溯的效果。构建过程使用了BFS（宽度优先搜索）算法。
搜索过程文字描述：
假设当前节点为temp, 我们找到temp的父节点，得到父节点的fail节点，再找到fail节点的所有子节点，寻找子节点中是否有和temp节点值相同的节点，若存在则temp的fail节点指向该节点，如不存在继续寻找该fail节点的fail节点，直到找到与相同值的节点或达到root节点。
符号描述：
temp:
1.temp=>father=>fail=>childs,
2.childs.foreach->(child -> if child==temp then temp->child),
3.if match_success then return else
4.temp=>father=>fail=>fail, if fail is root then temp->root else fail.childs and step 3
举例：
因此，最终我们得到的fail指针如图所示：
你会发现构建出来的fail指针实际跟KMP算法的next数组类似：图中/->s->h->e构成的she后缀he与/->h->e构成的he前缀he相同，she的e.fail指针指向he的e
第三步：模式匹配
匹配的核心是从目标串从头逐个开始，在ac自动机中进行匹配，匹配上的则计数，若未匹配上则跳转失配位置进行尝试匹配，直到全部匹配完成。
匹配的代码逻辑为：
定义p指针一开始指向root,然后开始遍历目标串的每个字符。
遍历过程：
1.假设当前目标串字符为i,当满足条件1(i不在p子节点中并且p也不是root节点)时，循环找p的fail节点直到不满足条件1
2.i在p子节点中，则p指向该节点，否则指向root节点
3.定义temp指向p,开始尝试匹配，若temp不是root节点，则进入循环否则跳出：
3.1若temp是模式串串尾，判断temp是否已经匹配成功过，若未匹配成功过则记该模式串匹配成功次数为1，否则在原成功匹配次数上加一
3.2将temp指向temp.fail
举例：匹配目标串asherp
匹配过程分解：
03python代码实现
作者原创，未经授权请勿转载
