如果当前失配了,不能像寻常一样直接跳 parent,这样是错的。题解都没有作具体说明,只是说每次使长度减一就是对的。更有甚者,题解写的是跳 parent,代码写的减一。这使新人(我)产生很多误解和疑惑。
实际上,我们每次询问,是提取了一个区间的 SAM,而这部分并不是完全意义的 SAM,同一个节点所表示的串的 endpos 集合可能并不相同,所以直接跳 parent 就会忽略一些串,产生错误的答案。正确的做法是每次使匹配长度减一,使得每种 endpos 都被遍历到。
望后人注意。