AC自动机
Trie树
概念
Trie又称单词查找树，或者前缀树。
它的根结点可以不包含字符。
节点中会标识到此节点是否构成一个单词。从根节点到此节点路径上的字符连起来为该节点对应的单词。
Trie树的实现
Trie树的构建也很简单，就是把每个单词的每个字母插入Trie。
比如上面图中插入”acc”，发现a已存在，继续，发现c边不存在，于是创建a的子节点c，继续创建c的子节点c。并在第二个c节点中标记是一个单词。
AC自动机
概念
AC自动机是在Trie树的基础上，加上了fail指针， 如果查询单词时匹配失败，则向fail指针指向的节点移动。这样就不用从头再找了。
如何构建AC自动机
首先让每个节点的fail指针为空，构建字典树，然后求解fail指针, 求解过程是BFS的过程
- 让根结点的所有子节点的fail指针指向根结点
- 其他节点的fail指针–指向—->它的父节点的fail节点的所有子节点中相同节点；如果没有相同的就指向根节点
实现思路就是构建树，设置fail指针，进行匹配搜索， Java实现代码较多，就不放出来了，感兴趣私聊。
AC自动机的原理
找到了一个单词结点后还应该看看有没有以该单词结点的后缀为前缀的其他单词，比如she的后缀he是单词he和her的前缀。因此就需要一个fail指针在发现失配的时候指向其他存在e的结点，来进行继续匹配
AC自动机的应用
基本问题：给出一个单词表，和一段文本串，问文本串中存在哪些单词以及个数。
高阶应用：结合词典树做特征工程，训练nlp分词模型