2938: [Poi2000]病毒

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

c++代码如下:

 

1 + 6 =