首页 > 其他分享 >AC 自动机学习笔记

AC 自动机学习笔记

时间:2024-07-28 21:30:15浏览次数:14  
标签:AC 前缀 trie ACAM tr 笔记 fail 自动机 节点

preface

第一次写 ACAM 模版是 2023.7.02,现在重新回顾了一下,还是有不少新的理解的,或者说一些概念更加清晰了。

1.引入

思考这样一个问题:

给若干模式串,求询问串中出现了多少个模式串。

暴力肯定是一一比对,复杂度是 \(O(n^2)\) 以上的,可以哈希一下,那复杂度就是 \(O(n^2)\)。

回想一下 kmp 算法解决的题目,暴力匹配也是 \(O(n^2)\),但 kmp 算法利用了询问串匹配时的最长相等前后缀来加快匹配,充分利用了询问串上的信息,做到优秀的 \(O(n)\) 复杂度。那上面这题可不可以用上面的思想呢。

首先可以把模式串都搬到 trie 树上,这样各个模式串相互的前缀信息就清楚了。显然 trie 树上每个节点都对应了一条到根节点的前缀。我们在 trie 树上也维护每个节点的最长相等前后缀,但这里的最长相等前后缀就不局限于这一条到根节点的前缀了,而是整棵 trie 树。那么现在可以简单理解为把 kmp 算法搬到 trie 树就有了 ACAM 算法。

2.实现

插入和 trie 树一样,不讲。

与 kmp 算法相同,ACAM 也有失配数组 \(fail_u\),方便我们在失配后找到一个最长的可以匹配的前缀。得到 \(fail\) 数组可以在 trie 树上 bfs。

void getfail() {
	std::queue<int> q;
	for(int i = 0; i < 26; i++) if(tr[0][i]) q.push(tr[0][i]);
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(int i = 0; i < 26; i++) {
			if(tr[u][i]) fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
			else tr[u][i] = tr[fail[u]][i];
		}
	} 
}

做到这一步就算建出了 ACAM 了,那么前面的题怎么做呢。

3.作用

尝试在 ACAM 上走询问串,假如走到节点 \(u\),它当然对应着一个前缀,并且意味着你成功匹配到了当前位置,即模式串中存在这么一段前缀。如果有一个模式串到这里就是终点,那么此时增加贡献。否则往上跳到 \(fail_u\),也对应一个前缀,并且它与 \(u\) 的后缀相同且最长,加上他的贡献,继续往上跳 \(fail_{fail_u}\)。

这样做是不重不漏的。因为这个过程相当于你固定了询问串上的右端点,查询从右端点开始有没有这样一段后缀是模式串。

更进一步,用 \((fail_u,u)\) 的边建出一张图,那么一定仍是一棵树。每个节点对应一段前缀,当前节点代表的字符串一定包含于子节点代表的字符串且是其一段后缀。

上面的暴力跳祖先复杂度太高,怎么优化?这个过程不就是求根到节点的链和嘛,求一下 \(fail\) 树上前缀和即可。

4.延伸

假如题目变成这样:

给若干模式串,求模式串中出现了多少个询问串。(保证询问串在模式串中出现过)

可以在 fail 树上考虑这个问题。因为题目的限制,他一定对应一个树上一个节点,那么它子树中的所有节点一定包含它(换句话说,如果子树中节点失配的话,一定会跳到它),所以就转化为子树求和做了。

5.思考

其实仔细想想,kmp 不就是一个模式串的 ACAM 吗?它的 trie 树是一条链,本质是相同的。

fail 树的包含关系非常重要。

如果加入一些修改操作,都有 fail 树了,就用数据结构维护树上问题呗。通常可以用 dfs 序转化为序列问题。

比如引入的问题中,如果加删字符串(前提是 ACAM 建出来了),就是一个单点加,求链和的问题,然后这个问题可以用树上差分转化为更简单的子树加,求单点,用树状数组维护。

延伸的问题里,同样的操作,只是修改变成了若干个单点修改,询问变成了求子树和。

ACAM 又提供了一个很好的状态表示,可以和 DP 结合。套路的设 \(f_{i,j}\) 表示考虑前 \(i\) 个字符,目前在 ACAM 上的 \(j\) 节点的答案。本质上是利用 ACAM 统计的模式串的某些信息来进行转移。

6.习题

P3041 [USACO12JAN] Video Game G

经典 ACAM + DP

设 \(f_{i,j}\) 表示考虑前 \(i\) 个字符,目前在 ACAM 上的 \(j\) 节点的最高分。转移就需要知道下一个字符能够匹配多少模式串,可以预处理出来。

复杂度 \(O(k\times tot)\)。

CF163E e-Government

经典的数据结构维护 ACAM 的题目,用上引出中的经典转化,需要实现子树加,单点求值。

CF1400F x-prime Substrings

ACAM + DP

需要发现 \(x-prime\) 字符串是很少的,因此将所有 \(x-prime\) 字符串一起建 ACAM,然后考虑 dp。设 \(f_{i,j}\) 表示考虑了前 \(i\) 个位置,在 ACAM 上状态为 \(j\),最少的删除次数使得原字符串不存在 \(x-prime\) 区间。转移不更新 \(x-prime\) 字符串的状态即可。

CF1202E You Are Given Some Strings...

考虑枚举断点 \(x\),前面给 \(s_i\),后面给 \(s_j\)。前者需要求出字符串 \(t\) 的每个前缀有多少 \(s\) 是其后缀,后者需要求出字符串 \(t\) 的每个后缀有多少 \(s\) 是其前缀。

前者是经典的 fail 树问题,后者翻转做一遍同样的事即可。

CF547E Mike and Friends

考虑离线,然后拆贡献,询问 \(s_k\) 在 \(s_{1...r}\) 中出现次数,询问 \(s_k\) 在 \(s_{1...l-1}\) 中出现次数,两者相减即可。

一边插入(若干单点加),一边计算答案即可(子树求和)。

CF587F Duff is Mad

上一题反过来,一下子不好做了。

如果是暴力的话,每次都要跑一遍 \(s_k\) 询问每个位置的价值,而 \(k\) 是可以重复的,于是 \(T\) 了。然后你想这个暴力一定能通过 \(s_k\) 长度小一点的数据,又观察到 \(\sum|s_i|\le 10^5\),所以考虑根号分治。

长度小跑暴力即可,长度大需要换一种角度。

如果考虑现在变成枚举每一个长度大的 \(s_k\),求它在区间 \([l,r]\) 的匹配情况。经典做法是从 \(s_k\) 的每个位置往上跳,看它可以跳到多少模式串,它可以转变为求所有模式串被询问串的所有位置跳到的次数和。如果长度记为 \(B\),那么这样的字符串总共不超过 \(\frac{m}{B}\),于是你标记 \(s_k\) 的所有位置,对整个 ACAM 求子树和,单次 \(O(m)\),询问前缀和后可以 \(O(1)\) 解决,于是就有了 \(O(\frac{m^2}{B})\) 的做法。

前面的做法复杂度是 \(O(qB\log m)\)。两者尽量均匀,解得 \(B=\frac{m}{\sqrt{q\log m}}\)。

总复杂度 \(\mathcal{O}(m\sqrt{q\log m})\)。

CF710F String Set Queries

二进制分组在线 ACAM

标签:AC,前缀,trie,ACAM,tr,笔记,fail,自动机,节点
From: https://www.cnblogs.com/FireRaku/p/18328895

相关文章

  • 高并发内存池(五)Thread Cache、Central Cache回收功能的实现
    目录一、ThreadCache的回收实现1.1ThreadCache回收框架1.2ThreadCache回收实现二、CentralCache2.1CentralCache回收框架2.2CentralCache回收实现一、ThreadCache的回收实现1.1ThreadCache回收框架在实现完整的高并发内存池内存分配逻辑以后,回收逻辑就变得......
  • KD-Tree 学习笔记
    KD-Tree学习笔记建树如果当前超长方体只有一个点,返回这个点选择一个维度(轮流)选择中位数(\(O(n)\))递归应用定理二维KDT中节点代表矩阵与任意一个矩形(边界上)有交的只有\(O(\sqrtn)\)个。证明:考虑一条直线,与KDT的交集,此层最多有两个,递归得到递归式,然后套主定理。......
  • 【esp32 学习笔记】(esp-idf 版本)从点灯开始——点亮LED
    【配置CMakeLists】首先配置自定义组件的CMake文件:components->led->CMakeLists.txt完整配置内容如下:file(TO_CMAKE_PATH"$ENV{IDF_PATH}"IDF_PATH) #将Windows下ESP-IDF的路径转化CMAKE路径idf_component_register(SRCS"led.c"          INCLUDE_......
  • Are Mobile DNN Accelerators Accelerating DNNs? - PPT
    AreMobileDNNAcceleratorsAcceleratingDNNs?-PPT1.pdf1.1.AssociationforComputingMachinery1.2.ResearchGate2.ACMMobiSys20212.1.TechnicalProgram-25June20212.2.FullpresentationReferences1.pdfAreMobileDNNAccelerato......
  • nand2tetris_hack计算机
    终于来到了这一步!!前文里,我们学习了hack编程语言,大概知道需要实现的hack计算机是什么样子,需要实现哪些功能。同时在更早的时候,我们建造了ALU和RAM组件,加上老师内置的ROM和键盘屏幕外设,那么开干!等一下,在开始之前,我想先聊聊当今通用计算机的体系结构,也就是大名鼎鼎的冯诺依曼体系,我......
  • 实战|Qt开发WordBN笔记软件#10 添加Font Awesome字体图标
    01背景【WordBN字远笔记】是天恩软件工作室开发的一款免费笔记软件;WordBN基于VS2019、Qt6.5开发,使用QtQuick(QML)开发语言。本课程将以【WordBN字远笔记】的界面为实战基础,详细介绍如何基于Qt/QML开发语言,从零开始开发一套真正的程序,包括国际化、版本发布、安装包制作等项目......
  • Django Web开发:构建强大RBAC权限管理系统的实战指南
    文章目录前言一、rbac基于角色的权限管理1.acl基于用户的权限管理2.rbac基于角色的权限管理二、应用示例1.配置角色资源a.分析表b.核心逻辑c.使用transfer在前端实现资源配置d.页面效果2.登录时获取对应权限a.员工登录b.中间件c.前端请求d.效果图3.前端-路由守卫......
  • ComfyUI插件:ComfyUI Impact 节点(二)
    前言:学习ComfyUI是一场持久战,而ComfyUIImpact是一个庞大的模块节点库,内置许多非常实用且强大的功能节点,例如检测器、细节强化器、预览桥、通配符、Hook、图片发送器、图片接收器等等。通过这些节点的组合运用,我们可以实现的工作有很多,例如自动人脸检测和优化修复、区域增强、......
  • Memcached跨平台性能解码:操作系统对缓存速度的影响
    Memcached跨平台性能解码:操作系统对缓存速度的影响在分布式缓存系统的设计和部署中,Memcached因其轻量级和高性能而成为首选方案之一。然而,Memcached在不同操作系统上的性能表现可能会有显著差异。本文将深入探讨这些差异的原因,并提供实际的测试方法和代码示例,帮助系统架构......
  • 机试笔记-2
    1.进制转换类问题反序数:比如输入123,输出321intmain(){intn;cin>>n;intans=0;while(n>0){ans=ans*10;ans=ans+(n%10);n=n/10;}cout<<ans<<endl;}10进制转x进制 输入100......