ACM 选手带你玩转 KMP 算法！( 三 ) _匹配

一个看不出啥规律，再来看 “ababc” ，同样比较指针指向最后一位的时候，出现不匹配：
对于前 4 位 "abab"首先找长度为 3 的公共前后缀，最长前缀是 “aba” ，最长后缀是 “bab” ，二者不相等；再找长度为 2 的，最长前缀是 “ab” ，最长后缀是“ab” ，二者相等，所以 “ababc”这个串的最长公共前后缀的长度 = 2 。
所以，模式串的滑动从最长前缀 ab 滑到了最长后缀 ab ，比较指针 j 从下标为 3 的位置开始重新比较。

文章插图
通过上面这两个图不知道你发现了规律没有：
比较指针 j 的所处的位置 =最长公共前后缀的长度 + 1 。
所以最后模式串 T = ababc 的 next 数组的值为下图：
至于第 1 个为什么是 0 ，你可以理解为当第 1 个不匹配的话，它的前面是没有任何元素的，记为-1 ，那么他这里的值就是 -1 + 1 =0 。
所以对整个模式串 T 求 next 值就齐活了。
如果你习惯从 0 开始，就是数组从 1 开始的结果每个值 -1：

# 代码从下标为 0 开始 。def getNext(T):# 后缀匹配指向i = 0# 前缀匹配指向j = -1# 初始化 next 数组next = [-1] * len(T)# 此处 next[0] = -1 ， 所以只需要求剩下的 len(T)-1 个即可while i < len(T)-1:# j == -1 就是找无可找 or 匹配成功 ， 相同前缀长度增加1if j == -1 or T[i] == T[j]:i += 1j += 1next[i] = j# 匹配不成功则在前面的子串中继续搜索 ， 直至找不到（即 j== -1 的情况）else:j = next[j]return next

匹配操作实现
那求出了 next 数组，我们就来拆分 KMP 模式串匹配的实现。
在这里主串用S = ，模式串用上文中求出的 T =为例(示例默认数组从下标为 1 开始) 。
从上图可以看出，第 1 次在 i = 4 ， j = 4 时出现不匹配，而此时 next 的值为 2 。
这就意味着，第 2 次，从模式串下标为 2 的位置和主串的当前位置的元素开始匹配，形式如下图。
上图发现还是不匹配，此时 next 的值为 1 ，这就意味着，第 3 次从模式串下标为 1 的位置和主串的当前位置的元素进行匹配，形式如下图。
然后开始的第 3 次。
看上图，第 3 次在 i = 6 ， j = 3 的时候出现不匹配，此时的 next 值为 1 ，那就意味着第 4 次是从模式串 j = 1 的位置与主串的当前位置进行匹配，形式如下图。
此时模式串和主串上的元素还是不匹配，此时 next 为 0 ，当 next 值为0 时，相当于是模式串的当前元素和主串的下一个元素进行比较，如下图。
然后有进行了第 5 次，发现匹配成功。

# 代码从下标为 0 开始def KMP(S, T):i = 0j = 0next = getNext(T)while i < len(S) and j < len(T):#j == -1 找无可找 ， 从 S[i+1] 开始和 T[0] 匹配 or 当匹配成功时 ， 往下匹配 。if j == -1 or S[i] == T[j]:i += 1j += 1# 匹配不成功则用 next(j) 找下一次匹配的位置else:j = next[j]# 如果模式串在主串中存在if j == len(T):return i - jelse:return -1

KMP 的讲解到这就全部结束了，真不容易呀，写了好久好久好久。
我自认为 KMP 全部讲清楚了，看懂了保你不管是初学，或者考试、面试都过过过。