AC 自动机

做法

核心在于维护失配指针，即每个节点指向 Trie 中存在的最长真后缀。

先建出 Trie 树。将根节点的后继节点加入作为起始节点 bfs。

bfs 的过程中，对于当前节点遍历字符集中的每个字符 $c$。

• 如果 $u$ 存在转移 $c$，那么这条转移的终点的失配指针应当指向 $u$ 的失配指针指向的节点向 $c$ 转移的结果，然后将这条转移的终点加入 bfs 队列。
• 如果 $u$ 不存在转移 $c$，那么新建一条向 $c$ 转移至 $u$ 的失配指针指向的节点向 $c$ 转移的结果。

不难发现从一个节点走向它失配指针指向的位置，它所代表的字符串的长度单调减少。因此从一个节点一直这样走，最后一定能够走到 Trie 的根节点。于是失配指针的关系构成了有根一棵树，以每个节点为根的子树即以这个节点为后缀的所有节点。