BZOJ 2938 [Poi2000] 病毒

发布于 2017-07-02  156 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2938

题意:给定一个二进制串字典,其中串定义为病毒串,一个串是安全的当且仅当:这个串无限长且其中不出现病毒串,求对于给定的病毒字典是否存在安全串


经典的 AC 自动机应用题... 考虑一个串是安全的实际上就是所有病毒串都不能在其中匹配到,如何满足无限这个条件呢,显然在 trie 图上匹配的路径能够形成一个环即可,这样一个环可以作为一个循环节无限重复。

那么建立 trie 图,标记不可以经过的节点,找环即可。有几个细节问题需要注意:

一个节点是危险节点不止当这个节点是某个病毒串的终止节点,还当这个节点的 fail 指向一个危险节点

可以直接使用一个节点的子节点记录 fail,因为我们是一定要尽可能让它失配的,这样可以节约不少编程复杂度

关于根节点的边界问题

板子不熟... 因为奇奇怪怪的错误调了将近 1h... 已经意识模糊了,代码有点丑...

 

 


一个非常弱的准退役OIER