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\) 的方案数,则有方程:
同时,可以根据 fail
来判出这个节点是否有成功的匹配,如果有,就可以跳过了
P2322 最短母串问题
不推荐上 LOJ
交这题,数据水的和那啥似的…
这题就如出一辙了,状压一下,然后就可以跳fail
找到匹配的串究竟是哪一个,就可以了
但这题卡空间,请注意空间常数
总结一下,acam
上 DP
是一类比较套路的题型,我们可以通过 acam
刻画出当前节点的匹配情况,然后进行 DP
就可以了
能不能再给力一点啊
众所周知,kmp
有一个叫失配树的东西,可以用来刻画两个前缀的最长公共 border
考虑将这个东西放到 acam
上,这就构成了 fail
树
fail
树有下列几个性质:
fail
树上的节点都是在trie
树上对应的前缀fail
树上一个前缀的祖先是在其他的模式串中出现过的后缀
然后就是一句看似像废话,但是实际上概括了 fail
树性质的话:子串一定是前缀的后缀
不懂的话,就先看题吧
P3796 AC自动机(加强版)
这里采用一个思想,主串实际上就是 fail
树上的若干节点
那这题就简单了,建出 fail
树对于,将主串拆分为若干节点并在节点上加一,对于每一个节点,统计其子树内的和就可以了
为什么呢,因为子串一定是前缀的后缀,对于这个前缀,他的子树内的节点一定是以自己为后缀的,所以自己一定出现在这个串内
P5357 AC自动机(二次加强版)
这题不用什么拓扑建图,直接拍上去一个fail
树,你就会惊喜地发现过了
P2414 阿狸的打字机
简化一下题意,给你多个字符串,询问第 \(i\) 个字符串在第 \(j\) 个字符串中出现的次数
这题也比较板子,可以在 trie
树上 dfs
,然后在 fail
树上加一,再处理询问就可以了
P5840 Divljak
题意:动态加入主串,求模式串中有多少个串可以与主串集合匹配
建出 fail
树,将主串分成节点,在节点上加一,在节点的祖先上统计子树和就可以了
但是这样有个麻烦,就是一个串可能被统计多次,所以要借助一下树论,将拆出来的节点按照 dfs
序排序,然后再在 lca
处减一就可以了