ac自动机 – Tgotp-Blog

3881: [Coci2015]Divljak

根据fail的性质克制,对于s建ac自动机后,查询t包含的串即为经过每个点的所有fail的权值和。

即fail会经过的点都被当前t所包含,那么建立fail树以后,就是查询s所在位置的子树有多少个点被不同t所经过。

用dfs序树状数组维护即可...

c++代码如下:
[crayon[......]

Read more

4861: [Beijing2017]魔法咒语

首先有不能含某个子串,那么容易发现使用ac自动机解决

对于前60%数据:

令f[i,j]表示构造到了第i个位置,目前位于ac自动机的第j个节点上。

有f[i+len[v]][to] += f[i][j]

那么很容易解决掉了这部分数据。

对于后40%数据:

因为考虑[......]

Read more

2434: [Noi2011]阿狸的打字机

首先容易根据给出的字符串建出trie树

对于查询(x,y),相当于对于y的每一个位置求出他的后缀是否包含x串

那么容易想到建立出ac自动机。

那么就是对于y串的每个位置,其能否通过fail到达x所在节点。

发现其实fail指针会构成一棵树,那么相当于统计在x节点下有多少点属于[......]

Read more

2938: [Poi2000]病毒

考虑如果已经有了一个无限长的串,那么现在就是判断这个串能不能合法。
对于所有串建立ac自动机,那么显然如果一个点是病毒,其以后的点都是病毒,
并且如果一个点的fail是病毒,那么这个点也应该是病毒。
在ac自动机上跑,如果能一直不经过所有标记过的点(即为环)那么一定存在这个串。

c++代[......]

Read more

3172: [Tjoi2013]单词

直接套上ac自动机模板。

然后倒序扫一遍就好了。

c++代码如下: