AC 自动机（简单版）题解

思路

逐个模式串在文本中匹配会重复扫描文本。把所有模式串插入一棵 Trie，并为每个节点建立失配指针，就得到 AC 自动机。失配指针指向当前前缀的最长真后缀所对应的 Trie 节点。

扫描文本时，自动机状态表示当前文本前缀的最长可匹配后缀。若在某状态停留过，则沿失配指针向上的所有终止节点所代表的模式串都出现过。

为了线性统计，先记录扫描文本时每个状态被访问的次数，再按构建失配指针时的 BFS 顺序逆序传播：把一个节点的访问次数加到它的失配父亲。传播完成后，某节点的计数大于零，当且仅当该节点代表的字符串在文本中出现过。终止节点保存以它结尾的模式串编号数，因此重复内容会按编号数正确累加。

做法

1. 把全部模式串插入 Trie，终止节点的计数加一。
2. BFS 构建失配指针，并补全每个状态的 26 个转移。
3. 扫描文本，每读一个字符转移状态，并增加该状态的访问次数。
4. 逆序遍历 BFS 序列，把访问次数传播到失配父亲。
5. 对所有访问次数大于零的节点，累加其终止计数。

证明

AC 自动机扫描到某个文本位置时，当前状态对应以该位置结尾的最长 Trie 前缀。沿失配指针不断跳转，恰好枚举该文本后缀中所有也是 Trie 前缀的字符串。因此一个模式串出现，当且仅当扫描过程访问过它的节点或失配树中的某个后代。

逆 BFS 顺序保证先处理失配树中的后代，再把访问次数加到父亲，所以传播后每个节点的计数等于其整个失配子树的访问总数。该值为正恰好表示对应模式串至少出现一次。终止计数等于在此结束的模式串编号数，累加它便对相同内容的不同编号分别计数。故算法输出正确。

复杂度

令 $L=|t|+\sum |s_i|$。时间复杂度为 $O(L\cdot 26)$（补全转移时含 26 的常数），空间复杂度为 $O(\sum |s_i|\cdot26)$。