首先，学AC自动机之前有必要掌握  Trie 图，KMP。

      AC自动机其实和KMP类似，它的fail指针就相当于KMP中的next指针，只不过fail指针是空间上的，而next指针是线上的。fail指针永远都指向层数比它低的对应节点，所 以它有比较多的性质， 比如 一直走fail 最后始终是会走到根节点的（必定失配），我们处理的时候是用bfs把fail加入到next 数组里面去的，所以next数组就已经包含了我们fail的指针。

     AC自动机还有一点就是end数组，用来保存信息的，储存那个位置是一个字符串的结束，这个模式串结束时间权值，匹配文本串和模式串就要用到这个数组。

     AC自动机的另一个知识点就是与DP相搭配，通常的情况是  dp[i][j]，i表示 文本串中的某一状态（可能是位置，或者状态压缩以后的值），j表示 AC自动机的状态。

     另外， AC自动机显然也是一个图，在这个图中我们也可以得到很多信息。例如bfs求两个字符串之间的距离。HDU 3247 Resource Archiver 。

AC自动机小结