假设我们有这样一个要求,一个字符串S,一个匹配字符串P,我们想知道匹配串P是否被包含在字符串S中,如果包含那它在S的什么位置上?...仔细观察匹配过程,我们发现第4行匹配过程中,当匹配到D时,虽然不匹配成功,但是我们是可以知道[D]元素前面的2个元素是[AB]和匹配串的前缀字符[AB]是匹配的,那我们之间比较第3个元素[C]就可以了,...当不匹配时,匹配串尽量少回溯,确定向右最大滑行距离
为达到这样的效果,要怎么做呢?...匹配成功
总结一下,通过辅助数组next[],确定整体匹配过程中,匹配串P的某个元素该与字符串S匹配,避免字符串S的指针回溯;
利用辅助数组next[],确定匹配失败时,后续匹配串该如何移动和重新比较,...注意: 真前缀和前缀的区别,真后缀和后缀的区别,
真前缀是不包括自身的,真后缀也是同理;
还是以字符book为例,
真前缀: b ,bo, boo
前缀: b ,bo, boo, book
真后缀:k,