首页 > 其他分享 >ACAM

ACAM

时间:2023-08-13 19:45:21浏览次数:32  
标签:匹配 前缀 acam 后缀 ACAM fail 节点

AC自动机

定义

定义 trie 树上的节点代表其形成的前缀

fail 树为 trie 树上的节点向被 fail 指针指向当前节点的点连边,形成的以 trie 树的根为根的树

\(son[\,i\,][\,now\,]\) 为 \(now\) 节点后加入字符 \(i\) 的转移节点

默认字符集为 \(O(1)\)

ACAM

解决多模式串的匹配问题

回想 kmp 的过程,最好的方法是找到一个 "border",但是这里的 border 的定义是定义在多个模式串上的,代表已经出现过的前缀中可以与当前后缀匹配的最长的前缀的节点

好吧,确实有些繁琐,如果还有不明白的,可以去这篇日报看看

好了,借助 acam,现在我们可以做到多模式串的匹配了

能不能再给力一点啊

不难看出,实际上,连完 fail 指针的 trie 树已经具备了描述当前后缀与模式串的前缀的匹配情况的能力了

举个例子,对于主串串的一个后缀而言,如果我们能够在模式串中找到一个前缀,使两者相等,那这个后缀就是对于匹配而言,就是有意义的,反之,无论这个后缀怎么扩展,都因为找不到与其相匹配的前缀而失配,所以我们可以直接抛弃这个后缀

上面的话实际上就是在描述主串在 trie 树上游走的过程,抛弃后缀实际上就是跳回根节点,而所有的匹配都可以通过跳 fail 来查到

所以acam的节点实际上描述了一类串的匹配情况,我们可以借助这一点,而解决一类与匹配有关的问题

P4052 文本生成器

正难则反,我们选择描述不与任何串匹配的状态,这样简单了不少

一个节点涵盖了一种状态,所以可以以 acam 的节点为主状态,进行 DP

定义 \(f_{i,j}\) 跳到 acam 节点 \(i\) 上,串长度为 \(j\) 的方案数,则有方程:

\[f_{son[\,i\,][\,now\,]\,,\,j+1}=\sum^{Z}_{i=A} f_{now,j} \]

同时,可以根据 fail 来判出这个节点是否有成功的匹配,如果有,就可以跳过了

P2322 最短母串问题

不推荐上 LOJ 交这题,数据水的和那啥似的…

这题就如出一辙了,状压一下,然后就可以跳fail找到匹配的串究竟是哪一个,就可以了

但这题卡空间,请注意空间常数

总结一下,acamDP 是一类比较套路的题型,我们可以通过 acam 刻画出当前节点的匹配情况,然后进行 DP 就可以了

能不能再给力一点啊

众所周知,kmp 有一个叫失配树的东西,可以用来刻画两个前缀的最长公共 border

考虑将这个东西放到 acam 上,这就构成了 fail

fail 树有下列几个性质:

  1. fail 树上的节点都是在 trie 树上对应的前缀
  2. fail 树上一个前缀的祖先是在其他的模式串中出现过的后缀

然后就是一句看似像废话,但是实际上概括了 fail 树性质的话:子串一定是前缀的后缀

不懂的话,就先看题吧

P3796 AC自动机(加强版)

这里采用一个思想,主串实际上就是 fail 树上的若干节点

那这题就简单了,建出 fail 树对于,将主串拆分为若干节点并在节点上加一,对于每一个节点,统计其子树内的和就可以了

为什么呢,因为子串一定是前缀的后缀,对于这个前缀,他的子树内的节点一定是以自己为后缀的,所以自己一定出现在这个串内

P5357 AC自动机(二次加强版)

这题不用什么拓扑建图,直接拍上去一个fail树,你就会惊喜地发现过了

P2414 阿狸的打字机

简化一下题意,给你多个字符串,询问第 \(i\) 个字符串在第 \(j\) 个字符串中出现的次数

这题也比较板子,可以在 trie 树上 dfs ,然后在 fail 树上加一,再处理询问就可以了

P5840 Divljak

题意:动态加入主串,求模式串中有多少个串可以与主串集合匹配

建出 fail 树,将主串分成节点,在节点上加一,在节点的祖先上统计子树和就可以了

但是这样有个麻烦,就是一个串可能被统计多次,所以要借助一下树论,将拆出来的节点按照 dfs 序排序,然后再在 lca 处减一就可以了

标签:匹配,前缀,acam,后缀,ACAM,fail,节点
From: https://www.cnblogs.com/Benzenesir/p/17627086.html

相关文章

  • loongnix下guacamole-server编译安装
    1、代码获取官网地址:https://guacamole.apache.org/doc/gug/troubleshooting.html代码获取地址:https://github.com/apache/guacamole-server/tags本地编译的版本:1.5.0......
  • Guacamole-server-1.4.0安装
    ##1.安装前准备###1.1系统环境本文档以CentOS7系统作为目标环境进行示范,系统具体版本信息如下:```shell..root@localh......
  • 远程桌面网关 guacamole 配置指南
    1.简介ApacheGuacamole是一个使用Web(H5)做为前端的远程桌面网关,支持对使用VNC、RDP、Telnet和SSH协议服务器的远程访问。一些开源的堡垒机(安全审计工具)也是集成该组件工具......
  • “Python 中的监督学习”Datacamp 课程回顾
    “Python中的监督学习”Datacamp课程回顾这是我刚刚参加的课程的回顾。这篇评论作为学习辅助:帮助我在第一次学习后综合信息,并希望将内容保留更长时间。这篇文章还提供了......