前置知识：KMP，trie。
一.自动机
这里的自动机都指有限状态自动机（DFA）。
一个 DFA 可以理解为一张有向图，由有限的状态（点），字母表，转移函数（边），开始状态与终止状态（起点，终点）组成。
AC 自动机就是一种在 trie 树的基础上，进行 KMP 算法中失配数组的计算，按照失配数组进一步建边，形成的有向图。也就是说，AC 自动机可以看成 trie 与 KMP 算法的结合体。
二.原理
首先看一下这么做的必要性：
- 【例一】多模匹配问题-P3808【模板】AC 自动机（简单版）
首先学过KMP的都知道，我们可以对于每个模式串跑KMP，复杂度 \(O(n^2+nm)\)。
但处理多个串信息的特点也很容易想到 trie，但 trie 无法完成快速匹配，失配后只能从头比较，复杂度也不容乐观。那可不可以将 trie 加上失配数组呢？
假设我们有几个字符串：
bxwhl
lol
bxpb
我们先建出 trie：
