KMP算法及其优化（超详解）

发布日期：2024-05-20 来源: 网络 阅读量（）

主串ABCDABBACABCDABD
子串ABCDABD
这时，我们发现子串的第7位（这里的位数指的都是从一开始的位数）与主串不同。
那么，我们下一次应该让主串哪一位与子串的哪一位进行比较呢？
由于子串的前6位与主串的前6位，已经比较过了我们已经知道了前6位所有的数字，我们当然不用再次比较。
给出假设，假如我们只知道子串的字母与顺序，对于主串我们只能得到哪一位等于或者不等于（只有等于了才能确定它的值）。
先不考虑算法的实现，用人工的方法考虑，最好的方式显然是用主串的第7位（虽然比较过，但我们不知道它是多少）与子串的第3位

进行比较。
主串ABCDABBACABCDABD
子串 ABCDABD
我们发现再次匹配失败，下一次要比较哪一位呢？
思考过后我们发现，第7位只能和第一位进行比较。
主串ABCDABBACABCDABD
子串 ? ABCDABD
我们发现，仍然不匹配，这时我们知道以第7位开头的主串的子串，不可能和我们我们寻找的子串相等了，我们需要比较主串下一位
和子串的第一位

因为我们一直都不知道主串出现不匹配的位置的字母是什么，所以我们每次遇到不匹配的位置，对子串的操作是完全一样的。
我们可以计算出每种不匹配情况下，下一次该比较哪一位。
子串 ABCDABD
下一次 0 111 1 2 3
我们思考，为什么能得到这样一个序列？
主串ABCDEF
子串ABCDA
主串ABCDEF
子串ABCDA
主串ABCDEF
子串?ABCDA
主串ABCDEF
子串?ABCDA
先看前4个，ABCD均不相同，如果这时候第五个不匹配，我们知道前四个都不一样，所以不论如何移动前四个都不能对的上
所以，只能下一次比较第一位。

主串ABCDABBACABCDABD
子串ABCDABD
主串ABCDABBACABCDABD
子串 ABCDABD
我们看之前的这个序列，之所以下次能够不从第一个开始，是因为我们发现AB和AB恰好可以对上。
我们得到结论：下一次访问的位置，由已经匹配了的字符的最长的后缀和前缀相等的长度决定。
我们的移动位置值是每次已经匹配的字符的最长的后缀和前缀相等的长度+1。
是因为要移动到已经匹配了的字符串的下一位
那我们怎么让计算机像我们一样，找到下一次该从哪里进行比较呢？
因为我们只知道子串的数据，只需将将我们得到的下一次要比较的位置记录下来即可。
这就是Next数组。下面给出代码实现：

KMP的过程和求Next数组的过程很像，但需要注意i,j都是从1开始的

子串 ABCDABD
Next 0 111 1 2 3
我们发现S[5]=‘A’(方便理解从第一位开始计数)
S[Next[5]]=‘A’
如果S[5]!=X 那么S[Next[5]]!=X也一定成立
我们发现进行了一次多余的比较，这时对Next数组进行修正。
使得Next[5]=Next[Next[5]]

得到新的Next
Next 0 1 1 1 0 1 3

此时有两种情况
第一种 j==0&&a[0]==已经遍历到的a的位置的元素a[i-1]
说明子串在这个位置时，的Next值为1且这一个元素和子串第一个元素相等，那么它下一次回溯到的元素是第一个，
由于它和第一个元素一样，所以也让Next_val[i]=Next_val[j]=0
第二种

综上所述，前一位和这一位检测的作用：前一位确定这一位之前已经匹配的长度，这一位则确定回溯位置的元素和这一位的元素是否相同，判断Next数组是否需要修正

KMP过程一模一样，只有Next数组不一样