KMP再思考:为什么要用最长公共前后缀,为什么要用公共前后缀

1.如果不用最长的,则会丢失可匹配部分,也就是本来可能匹配的,结果却不能匹配。

2.因为需要保证比较位置之前的字符串都一致了,如果不用公共前后缀,则可能导致比较位置之前的字符串不一致。

理由其实很简单,因为把前缀移到后缀的位置,而比较指针不变,如果后缀(这时已经不是真正的后缀了)的结束不是贴着比较指针的话,就

不能保证比较指针前的字符和待比较串一致。

选择公共前缀是必定的,因为如果想要在待比较串中找出模式串,那么一定要和模式串的开头匹配,也就是和前缀匹配。

但是选择的不是公共后缀的话,也就是结尾不贴近比较指针的话,就会导致上面的问题。

3.就算使用最长串,是否还是会有遗漏的情况存在呢?

那么我们可以假设使用最长串,看看有没有遗漏的情况发生。

假如在过程中发生了匹配。所谓的匹配是指在比较指针之前要和待比较串完全匹配,如果不完全匹配就没有意义,下图的红色框和长的绿色框是假设的匹配情况。

但是根据我们 公共前后缀的定义,应该出现如下的最长公共前后缀,所以这种匹配如果存在,只能说明我们之前找的不是最长公共前后缀,比公共前后缀短。

但是当前情况下,并不成立,因为两者根本不相等。如果是相等的话,就会如上所言,之前找到的不是最长前后缀。

原文地址:https://www.cnblogs.com/lqlqlq/p/13327682.html