ac自动机 – Tgotp-Blog

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++代码如下: