个人感觉这里应该是一个小优化吧?
或者说这是Trie图这种AC自动机的实现方式的一个必要步骤
首先这里加一条边的正确性是可以保证的,因为fail连向的节点一定是当前节点的一个后缀,那么这样连下去,在匹配的时候遇到当前节点并没有对应的儿子时,就可以通过加的这条边去到另一个可能匹配的位置
大概类似于“我的后缀的一个延伸,也是我的一个延伸”
by Orion545 @ 2018-05-10 15:13:43
@[KamijouIndex](/space/show?uid=27753) 谢谢
by 天上一颗蛋 @ 2018-05-10 20:02:53
@[KamijouIndex](/space/show?uid=27753) 其实这里是因为失配过程太复杂了。所以其实这里是把AC自动机魔改了。这样,原本在`find`中的一个`while`循环就可以删除
by constructor @ 2018-05-15 16:43:16
@[constructor](/space/show?uid=56461)
soga
怪不得我之前听学长说这东西不是纯血统AC自动机,原来有这一层原因
不过能实现目的的算法就是好算法!
by Orion545 @ 2018-05-15 22:24:49
考古
by team109 @ 2020-01-19 12:20:27