【算法】kmp 的 getnext 函数解释

本文主要是介绍【算法】kmp 的 getnext 函数解释，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本人的理解，供参考，如有错误请指出谢谢

设子串：ababafgda

getnext 函数的目的就是找出子串的子串的共同前后缀的长度

设变量
j = 0：
k = 1：表示循环进度，也表示当前在那个子串的子串
len = strlen(子串) = 9

while(k < len - 1)

匹配失败
k++ ，进入下一个子串，在 +1 之前 k 表示的是 ab 子串
j = 0，肯定要归零，要不然怎么找前缀

匹配成功
此时 k = 2，就表示aba子串，那么aba子串的公共最长前后缀就是 1，这个 1 只能从 j 变量获得，此时 j = 0，所以
next[k] = j+1
就是说 aba子串的公共最长前后缀就是 1
匹配结束进入下一个子串，所以 k++，所以不论成功与否 k 都是要+1的
那么 j 呢，也是要 +1 的
为什么？

aba
要获得 aba 的前后缀需要比对 ab 中的a 和 ba 中的b 的匹配和 ab中的b 和 ba 中的a 的匹配

这里需要分两种情况

如果 ab 是匹配成功的，那么ba 就是 ab 各自下标的+1的偏移
如果不匹配就需要从头开始匹配
显然 ab 是不匹配的，所以就需要匹配 ab 的a 和ba 的 a，如果成功就说明 aba 的公共最长前后缀就是 1，不成功就是0咯

例如：abab
aba 中 ab 的a 和ba 的 a 是匹配的（见上面），所以接下来就该匹配两个b 了，这两个b 的下标就是aba 中两个a 的下标+1

之后重复下标+1和归零的操作即可

匹配成功
abab 的公共最长前后缀就是 aba 公共最长前后缀 +1

有没有发现 aba 的公共最长前后缀是前缀也就是 j+1
aba 是 j 指向 a，值就是 0 ，所以需要 +1之后才能赋值给 next
但在 abab中 j 指向 aba 中的 b，值就是1，也需要 +1之后才能赋值给 next
所以可以先 +1 在赋值给next