AC自动机小结
AC自动机小结
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132818609
AC自动机是一种多模匹配算法。
常见操作
查询一个串的子串
任何一个串的子串都可以表示成他的一个前缀的后缀
他的前缀可以在Trie树上查询
后缀相当于其在fail树上的所有祖先
例1 ： HDU4117
接上。首先AC自动机要学会离线。
对于每个点查询祖先复杂度很大。但其实可以每个祖先计算其对子树的贡献。
而这个过程可以对fail树的dfn序建线段树维护
例2 ：HDU4787
这题不能离线了。
但其实可以对AC自动机根号重构。
例3 ：Gym- 104542F
和例1类似
只不过离线变成了kruskal重构树
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-11
Kruskal重构树+AC自动机+树状数组：Gym - 104542F
Kruskal重构树+AC自动机+树状数组：Gym - 104542F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132818179 https://vjudge.net/contest/579844#problem/F 看到连边和没有强制在线，考虑Kruskal重构树 看到判断子串，考虑AC自动机+线段树 然后要非常大胆地把两个结合起来。 然后就是大码量了。 具体总结一下流程： 先建出Kruskal重构树 对Kruskal重构树处理...
2023-09-11
根号重构AC自动机：HDU4787
根号重构AC自动机：HDU4787 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132812068 https://acm.hdu.edu.cn/showproblem.php?pid=4787 每次重构AC自动机复杂度非常大，但其实可以根号重构 维护两个AC自动机，一个大，一个小，然后对操作序列分块 小分块维护当前块的AC自动机，每次操作都重构 大分块维护之前的AC自动机，每 q\sqrt qq 次操作重构 对于任意不支持修改数据结构，都可以根号重构 ...
2023-09-11
离线建AC自动机维护子串+线段树维护AC自动机：HDU4117
离线建AC自动机维护子串+线段树维护AC自动机：HDU4117 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132804430 https://acm.hdu.edu.cn/showproblem.php?pid=4117 离线处理 AC自动机每次插入都要重构，但其实可以先离线建好，再进行操作 AC自动机理解——维护子串 每个子串都可以表示成一个前缀的一个后缀。 任意一个前缀是Trie树上的一个点，然后其对应后缀就是fail树上的祖先 fail树本质是一个...
2026-06-17
算法复键——AC自动机
算法复键——AC自动机 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162074359 什么是AC自动机： 在Trie上跑kmp 核心思想：构建fail树。fail[u]指向一个节点，表示这个节点具有和u所在节点所代表串的最长公共后缀。 核心代码： 12345678910111213141516171819void bfs() { int i, j; q.push(1); fail[1] = 0; fail[0] = 1; // 根节点失配指向...