KMP算法

规定

• 字符串均由 字符型数组 储存，且起点数组为1。
• a(1)为下标为1的a，a(2）为下标为2的a。

最长公共前后缀？

前缀？后缀？

以原字符串起点为起点的子串（非自身）称为父串的一个前缀。

以原字符串终点为终点的字串（非自身）称为父串的一个后缀。

如：abcde

其前缀：abcd，abc，ab，a；

其后缀：bcde，cde，de，e；

公共前后缀？最长公共前后缀？

当前缀和后缀相同时，被称为（一对）公共前后缀。

长度最长的公共前后缀被称为 最长公共前后缀。

如：ababa

公共前后缀有：a，aba；注意，ab，ba并非公共前后缀，只有前缀和后缀大小和字符顺寻都严格相等时才被称为公共前后缀。

其最长公共前后缀为：aba

模式串的next数组

next数组长度 与 模式串长度 相同，next数组中的元素与模式串的字符时一一匹配的。

next数组第i个元素的值为 模式串从1到 i 区域内 最长公共前缀的长度。

如上，模式串str[]为ababaa

next[1]等于模式串str[]从1到1区域内(a)，最长公共前后缀，则为0

next[2]等于模式串str[]从1到2区域内(ab)，最长公共前后缀，则为0

next[3]等于模式串str[]从1到3区域内(aba)，最长公共前后缀，则为1

next[4]等于模式串str[]从1到4区域内(abab)，最长公共前后缀，则为2

next[5]等于模式串str[]从1到5区域内(ababa)，最长公共前后缀，则为3

next[6]等于模式串str[]从1到6区域内(ababaa)，最长公共前后缀，则为1

KMP过程

相比于BF算法，KMP的next数组可以帮助我们实现一次跳跃多个（模式串的）字符。

为什么可以？

next指针的含义

next[i] 表示在模式串从1到i区间内 最长公共前后缀 中 前缀的最后一字符所在的位置。

str[i]的值与str[next[i]]的值是相等的。

因为前后缀是相同的，后缀能匹配上时，将前缀移动后缀的地方，也是可以匹配上的。