本文是博主自身对AC自动机的原理的一些理解和看法，主要以举例的方式讲解，同时又配以相应的图片。代码实现部分也予以明确的注释，希望给大家不一样的感受。AC自动机主要用于多模式字符串的匹配，本质上是KMP算法的树形扩展。这篇文章主要介绍AC自动机的工作原理，并在此基础上用Java代码实现一个简易的AC自动机。
欢迎探讨，如有错误敬请指正
1. 应用场景—多模字符串匹配我们现在考虑这样一个问题，在一个文本串text中，我们想找出多个目标字符串target1,target2,……出现的次数和位置。例如：求出目标字符串集合{"nihao","hao","hs","hsr"}在给定文本"sdmfhsgnshejfgnihaofhsrnihao"中所有可能出现的位置。解决这个问题，我们一般的办法就是在文本串中对每个目标字符串单独查找，并记录下每次出现的位置。显然这样的方式能够解决问题，但是在文本串较大、目标字符串众多的时候效率比较低。为了提高效率，贝尔实验室于1975年发明著名的多模字符串匹配算法——AC自动机。AC自动机在实现上要依托于Trie树（也称字典树）并借鉴了KMP模式匹配算法的核心思想。实际上你可以把KMP算法看成每个节点都仅有一个孩子节点的AC自动机。
2. AC自动机及其运行原理2.1 初识AC自动机
AC自动机的基础是Trie树。和Trie树不同的是，树中的每个结点除了有指向孩子的指针（或者说引用），还有一个fail指针，它表示输入的字符与当前结点的所有孩子结点都不匹配时(注意，不是和该结点本身不匹配)，自动机的状态应转移到的状态（或者说应该转移到的结点）。fail指针的功能可以类比于KMP算法中next数组的功能。
我们现在来看一个用目标字符串集合{abd,abdk, abchijn, chnit, ijabdf, ijaij}构造出来的AC自动机
上图是一个构建好的AC自动机，其中根结点不存储任何字符，根结点的fail指针为null。虚线表示该结点的fail指针的指向，所有表示字符串的最后一个字符的结点外部都用红圈表示，我们称该结点为这个字符串的终结结点。每个结点实际上都有fail指针，但为了表示方便，本文约定一个原则，即所有指向根结点的 fail虚线都未画出。
从上图中的AC自动机，我们可以看出一个重要的性质：每个结点的fail指针表示由根结点到该结点所组成的字符序列的所有后缀 和 整个目标字符串集合（也就是整个Trie树）中的所有前缀 两者中最长公共的部分。
比如图中，由根结点到目标字符串“ijabdf”中的 ‘d’组成的字符序列“ijabd”的所有后缀在整个目标字符串集{abd,abdk, abchijn, chnit, ijabdf, ijaij}的所有前缀中最长公共的部分就是abd，而图中d结点（字符串“ijabdf”中的这个d）的fail正是指向了字符序列abd的最后一个字符。
2.2 AC自动机的运行过程：
1）表示当前结点的指针指向AC自动机的根结点，即curr = root
2）从文本串中读取（下）一个字符
3）从当前结点的所有孩子结点中寻找与该字符匹配的结点，
若成功：判断当前结点以及当前结点fail指向的结点是否表示一个字符串的结束，若是，则将文本串中索引起点记录在对应字符串保存结果集合中（索引起点= 当前索引-字符串长度+1）。curr指向该孩子结点，继续执行第2步
若失败：执行第4步。
4）若fail == null（说明目标字符串中没有任何字符串是输入字符串的前缀，相当于重启状态机）curr = root, 执行步骤2，
否则，将当前结点的指针指向fail结点，执行步骤3)
现在，我们来一个具体的例子加深理解，初始时当前结点为root结点，我们现在假设文本串text = “abchnijabdfk”。