关于此题 SAM 题解
查看原帖
关于此题 SAM 题解
83337
wwlw楼主2021/6/3 17:33

如果当前失配了,不能像寻常一样直接跳 parent,这样是错的。题解都没有作具体说明,只是说每次使长度减一就是对的。更有甚者,题解写的是跳 parent,代码写的减一。这使新人(我)产生很多误解和疑惑。

实际上,我们每次询问,是提取了一个区间的 SAM,而这部分并不是完全意义的 SAM,同一个节点所表示的串的 endpos 集合可能并不相同,所以直接跳 parent 就会忽略一些串,产生错误的答案。正确的做法是每次使匹配长度减一,使得每种 endpos 都被遍历到。

望后人注意。

2021/6/3 17:33
加载中...