从功能上来说，AC 自动机是可以求解多个小串 $A$ 在多个长串 $B$ 的中是否出现过、出现的次数和每一次出现的位置。从具体实现上来说，AC 自动机就是在 trie 树上跑 KMP。其时间复杂度为线性的，是 $O(\sum\lvert A\rvert+\sum\lvert B\rvert)$ 。

AC 自动机的失配指针与 KMP 的 $nxt$ 数组极为相似，可以参考理解。如果节点 $i$ 的失配指针为 $j$，那么从根节点到 $j$ 的边上的字符形成的字符串应该与从 $i$ 出发向根节点行进 $dep_j$ 步到达的点 $k$ 再从 $k$ 走到 $i$ 边上的字符形成的字符串一样，在满足 $i\ne j$ 的前提下，应该使 $dep_j$ 尽可能的大。

对于上图，$9$ 号节点的失配指针之所以是 $2$ 是因为从根节点到 $2$ 好节点边上的字符串 $\texttt{he}$ 与从 $7$ 号节点到 $9$ 好节点边上的字符串 $\texttt{he}$ 是一样的。