应用场景
AC自动机与trie图, 都是求一堆字符串在一个文本中出现的次数.
(建trie树时, 建成AC自动机求匹配数量的时间复杂度为$O(n)$, 建成trie图的时间复杂度为$O(n/Σ(字符集)的大小)$)
概念解析
状态机(就是自动机): 一个有向图, 每个点代表一个状态.
ac自动机就是trie树加上非补全next指针(不存在的节点直接pass掉, next指针没有指向即不存在)
trie图就是trie树加上补全next指针
fail树就是建完fail指针之后, 去掉trie树, 并将fail指针逆向, 剩下的树形结构. 即为fail树
详解博客
AC自动机与KMP
(注意, 无论是kmp, 还是AC自动机中的前后缀都是指的非平凡(不含字符串本身的前后缀集合)前后缀)
- 前者是trie树上求next数组, 进行匹配, 后者是一维线性串上求next数组.
- AC自动机中的前缀, 根节点指向任意一个节点的串(所有前缀), 后缀是指某个节点在其到根节点路径上的某一个节点连成的串.
- AC自动机的ne数组的含义, 最长前缀与后缀相等的尾节点编号.
- 字符串就是特殊的trie, 一条链的trie. KMP就是特殊的AC自动机.
- KMP每次只能匹配一个串, AC自动机一次可以匹配多个串.
- 我们可以发现在求next数组时, KMP是由next[i - 1]来算的, 由前面的多个点的next值来算i的next值. 类比到AC自动机, 我们第i层的next值是由前i - 1层来算的 -> bfs建next数组
// KMP 这颗trie树为一条链
for (int i = 2; i <= m; i ++ )
{
int j = ne[i - 1]; // 见第6行, 新循环i++了, 所以j = ne[i - 1]
while (j && p[i] != p[j + 1]) j = ne[j]; // 看j的儿子节点中是否有值等于p[i]的节点
if (p[i] == p[j + 1]) j ++ ; // 走到节点j儿子节点上去
ne[i] = j; // 更新树中节点i的next值
}
// AC自动机与KMP一一对应
while(hh <= tt)
{
int t = q[hh ++ ];
for(int i = 0 ; i < 26 ; i ++ ) // 枚举t的所有儿子节点的值 KMP只有与一个儿子节点无须枚举
{
c = tr[t][i]; // t的儿子节点中值为i的节点的编号
j = ne[t]; // 上一个字母的前缀到哪了
while(j && !tr[j][i]) j = ne[j];
if(tr[j][i]) j = tr[j][i];
ne[c] = j;
q[++ tt] = c; // 拓展出来了的点就放入队列
}
}
Trie图的优化思想(fail指针的补全)
原来需要一下一下跳直到找到可匹配前缀, 现在通过累积维护, 一层一层更新, 可以一步直接找到可匹配前缀的下标.
