AC自动机算法详解与多模式匹配性能对比评测

AC自动机的核心用途是什么？它在字典树（前缀树）上实现了类似KMP的失败转移机制，专为高效的多模式串匹配而设计。

假设你有一组敏感词（字符串数组），并给定一篇长文本，AC自动机能够快速扫描并报告其中出现的所有敏感词。它是构建更复杂模式匹配算法的基础模块，掌握AC自动机的原理后，学习后续算法将更加顺畅。

核心构建步骤

首先将敏感词集合构建成一棵字典树（前缀树）。字典树由字符边连接节点，每条从根到叶的路径对应一个字符串。但AC自动机对标准字典树进行了增强：每个节点额外维护一个 失败指针（fail指针）（通常用虚线表示）。根节点的失败指针指向空，且根节点的直接子节点的失败指针强制指向根节点。

那么下层节点的失败指针如何确定？

具体流程：构建完整的字典树后，采用广度优先遍历（BFS）逐层计算每个节点的失败指针。举例说明：假设节点X的父节点有一条指向X的边（字符'b'），而父节点的失败指针指向根节点。根节点虽然有通往'a','b','c'的边，但不存在字符'b'对应的子节点。因此，从父节点的失败指针（根节点）继续查找，根节点的失败指针为null，null没有子节点，所以节点X的失败指针直接指向根节点。

再看另一个节点X（图中不同位置）。其父节点到X的边字符为'd'，但父节点的失败指针指向根节点，而根节点没有'd'对应的子节点，因此X的失败指针同样指向根节点。

第三个节点X（按BFS顺序处理）。父节点到X的边字符为'c'，父节点的失败指针指向根节点，而根节点恰好存在字符'c'对应的子节点，因此X的失败指针指向该子节点。

失败指针设置规则

总结规则如下：

1）根节点的失败指针指向 null；

2）根节点的直接子节点的失败指针指向根节点；

3）对于其他节点：从父节点的失败指针开始，沿失败指针链回溯，直到找到一个节点，其子节点包含当前字符，则当前节点的失败指针指向该子节点；若回溯到null仍未找到，则失败指针指向根节点。

AC自动机失败指针的实质含义

理解并不复杂：当匹配失败时，我们需要在当前已匹配文本中，找出一个最长的后缀，该后缀恰好是某个模式串的前缀。失败指针指向的节点正是这个“最长可匹配前缀”的终点。这样，下次匹配可以从该节点继续，无需回退文本指针——这与KMP的思想一致，只不过KMP处理的是线性字符串，而AC自动机处理的是树形结构。