【笔试题心得】关于KMP在笔试中的题型

好几家都考到KMP了问的比较多的是 next数组 ，其实KMP的相关机制我在代码随想录算法训练营第九天|KMP算法_菜鸟的Zoom之旅的博客-CSDN博客中写道过，现在在复习一下，由于next数组的定义其实会有所歧义（有些程序中会直接将前缀表作为next），故这里写明个个环节中next数组的值。

这里对KMP进行一个回顾
（摘抄自KMP算法解析_caccbacbb 使用kmp算法next_秋之颂的博客-CSDN博客）

1) 首先回顾一下前缀和后缀的概念：

对于一个字符串，其前缀是指其所有头部子串（包括本身）构成的集合，而“真前缀”就是不包括其本身的所有头部子串构成的集合，可以参考子集和真子集的比较。
同样，后缀是指其所有尾部子串（包括本身）构成的集合，而“真后缀”就是不包括其本身的所有尾部子串构成的集合，注意，不论前缀还是后缀，其字符排列顺序都是从左至右，与原串相同，下面举例说明：

对于串“abacab”，
其前缀是{a, ab, aba, abac, abaca, abacab}，真前缀是{a, ab, aba, abac, abaca}；其后缀是{abacab, bacab, acab, cab, ab, b}，真后缀是{bacab, acab, cab, ab, b}.

(2) 接下来，回顾一下最长相等真前后缀长度的概念：

最长相等真前后缀长度即某串真前缀与真后缀做交集后，集合中最长的串的长度，

以串“ababa”为例：
对于串“ababa”，其真前缀{a, ab, aba, abab}与真后缀{baba, aba, ba, a}的交集为{a, aba}，其中“aba”最长，为3，因此串“ababa”的最长相等真前后缀长度为3

(3) KMP算法流程

这里先不具体解释第“（1)、(2)”步到底在干什么，因为很难理解，等按照以下步骤，再加上后面的实例走一遍，就差不多可以理解了。

i. 计算模式串的所有前缀的最长相等真前后缀长度；
ii. “i.”中所有长度构成部分匹配值（PM）数组（其实也就是前缀表），每一个值对应一个字符；
iii. 部分匹配值按位右移，左边用-1补齐，再统一加1，得到Next数组；
iv. 在匹配过程中，如果在模式串的某个字符出现失配，以该字符对应的Next值跳到模式串相应位置，再与主串当前位置进行比较；
iv. 重复以上过程直至完全匹配成功或者匹配失败，结束程序。

标红的部分清晰的说明了Next数组的求解方式。

下面举一个例子：