这题的dfs是如何解决两个循环节拼出一个病毒串的情况的?

P2444 [POI2000] 病毒

无论如何,一个串与多串的匹配相当于再trie图上的节点上走。如果说图上删除被标记的节点仍然存在环,那就证明可以有无限长的。 比如你这个例子,010010010在1001上匹配,第一次的0适配后返回根节点,然后接下来的1001就会匹配上,不是合法串。
by Richard_Whr @ 2024-02-08 11:50:11


|