KMP算法是一种改进的字符串匹配算法，如果不研究编码的话，手工实现还是比较简单，小型字符串甚至不需要你去求 next 数组就能看出来怎么移动。但是会有一些题目让你求解 next 数组，这里就以一个题目讲一下手工求解的过程。
例：求串 ‘ababaaababaa’ 的 next 数组
观察第一个元素，它没有前缀和后缀（串本身不能作为前缀或后缀），所以记录数据为0（这个数字表示当存在前缀和后缀相同的情况下，所能包含的最大的元素）
观察前两个元素，前缀为a，后缀为b，不相同，即没有相同的前缀和后缀，所以同样记录数据为0
观察前三个元素，存在前后缀相同的情况，为a，记录数据为1
观察前四个元素，同样存在前缀后缀相同的情况，为ab，记录数据为2
观察第五个元素，相同的前后缀为aba（ababa、ababa），记录数据为3
同理观察余下的（用加粗表示前缀、下划线表示后缀）
ababa_a_ 1
ababaa_a_ 1
ababaa_ab_ 2
ababaa_aba_ 3
ababaa_abab_ 4
ababaa_ababa_ 5
ababaaababaa 6
最后我们得到一组数值：0 0 1 2 3 1 1 2 3 4 5 6
在这组数开头添加 -1，并删去最后一个数值，数组变为： -1 0 0 1 2 3 1 1 2 3 1 1 2 3 4 5
所有值+1，变为：0 1 1 2 3 4 2 2 3 4 2 2 3 4 5 6，这就是我们需要的 next 数组
需要注意的是，不同的题目next[0]可能为-1，所以 -1 0 0 1 2 3 1 1 2 3 1 1 2 3 4 5 同样有可能作为 next 数组，但是这两种一定不会同时出现。
题目图片：
image
网友评论