本文共 3305 字，大约阅读时间需要 11 分钟。
引言
KMP原文最初写于2年多前的2011年12月，因当时初次接触KMP，思路混乱导致写也写得非常混乱，如此，留言也是骂声一片。所以一直想找机会重新写下KMP，但苦于一直以来对KMP的理解始终不够，故才迟迟没有修改本文。
然近期因在北京开了个算法班，专门讲解数据结构、面试、算法，才再次仔细回顾了这个KMP，在综合了一些网友的理解、以及跟我一起讲算法的两位讲师朋友曹博、邹博的理解之后，写了9张PPT，发在上。一不做二不休，索性将PPT上的内容整理到了本文之中。
KMP本身不复杂，但网上大部分的文章（包括本文的2011年版本）把它讲混乱了。下面，咱们从朴素匹配算法讲起，一步步从字符串的前缀后缀引入next数组，最后利用next 数组进行匹配，希望让大家对KMP有一个清晰的了解。
朴素匹配算法
咱们先来看朴素匹配算法。假设现在原始串S串匹配到 i 位置，模式串T串匹配到 j 位置
- 如果当前字符匹配成功，即s[i+j] == T[j]
-
- i 不变，j++，继续匹配下一个字符
- 如果失配，即S[i+j]! = T[j]
-
- 令i++，j = 0，即每次匹配失败时，模式串T相对于原始串S向右移动一位。
换言之，只要模式串匹配失败，那就往右边移动一位，简单直接，也干脆暴力。
假定原始串S串为“acaabc”，模式串T 串为“aab”，那么模式串去匹配原始串的整个过程如下图所示：
那KMP做了什么改进呢？KMP其实是在一步步往后匹配的过程中，后面的匹配会设法利用前面的匹配信息，从而减少不必要的匹配。
KMP算法
原理
- 假设现在原始串S串匹配到 i 位置，模式串T串匹配到 j 位置
-
- 如果当前字符匹配成功，即S[i] == T[j]
-
- 令i++，j++，继续匹配下一个字符；
- 如果失配，即S[i] != T[j]
-
- 令i不变，j = next[j]，(next[j] <= j - 1)，即模式串T相对于原始串S向右移动了至少1位（换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值，即移动的实际位数：j - next[j] > =1）
步骤
- ①寻找最长前缀、后缀
-
- 对于Pj = p0 p1 ...pj-1 pj，查找字符串Pj的最大相等k前缀和k后缀
-
- 即查找满足条件的最大的k，使得p0 p1 ...pk-1 pk = pj-k pj-k+1...pj-1 pj。如果给定的模式串为“abaabcaba”，那么它的各个前缀后缀的公共元素的最大长度值如下表格所示：
- ②求next数组
-
- 根据第①步骤中求得的各个最大前缀后缀的公共元素长度求得next 数组，相当于前者右移一位且初值赋为-1，如下表格所示：
- ③匹配失配
-
- 向右移动位数：j - next[j]
-
- 注：j 是模式串中失配字符的位置，且 j 从0开始计数。
前缀后缀
基于《最大长度表》匹配
失配时，模式串向右移动的位数为：已匹配字符数 - 失配字符的上一位字符所对应的最大长度值
下面，咱们就结合之前的最大长度表和上述结论，进行字符串的匹配。如果给定原始串“BBC ABCDAB ABCDABCDABDE”，和模式串“ABCDABD”，现在要拿模式串去跟原始串匹配，如下图所示：
- ①当模式串最后一个字符D跟原始串匹配时失配，显而易见，模式串需要向右移动。但向右移动多少位呢？
-
- 如果利用最原始的朴素匹配算法，那么把模式串不断的向右移动一位，直到全部字符实现匹配；
- 事实上，因为此时已经匹配的字符数为6个（ABCDAB），然后根据《最大长度表》可得字符B对应的长度值为2，所以根据之前的结论，可知需要向右移动6 - 2 = 4 位。
- ②模式串向右移动4位后，发现C处再度失配，因为此时已经匹配了2个字符（AB），且上一个字符B对应的最大长度值为0，所以向右移动：2 - 0 =2 位。
- ③A与空格失配，向右移动1 位。
- ④继续比较，发现D与C 失配，故向右移动的位数为：已匹配的字符数6减去上一位字符B对应的最大长度2，即向右移动6 - 2 = 4 位。
- ⑤经历第④步后，发现匹配成功，过程结束。
最大长度表引出next 数组
由上文，我们已经知道，字符串“ABCDABD”各个前缀后缀的最大公共元素长度分别为：
而且，根据这个表可以得出下述结论
- 失配时，模式串向右移动的位数为：已匹配字符数 - 失配字符的上一位字符所对应的最大长度值
把next 数组跟之前求得的最大长度表对比后，不难发现，next 数组相当于“最大长度值” 整体向右移动一位，然后初始值赋为-1。意识到了这一点，你会惊呼原来next 数组的求解竟然如此简单！从而有
失配时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值
而后，你会发现，无论是基于最大长度表的匹配，还是基于next 数组的匹配，两者得出来的向右移动的位数是一样的。不信的话，咱们可以来看看具体过程。
基于《next 数组》匹配
下面，我们来基于next 数组进行匹配。
- ①匹配到字符D时失配，由于 j 从0开始计数，故数到失配的字符D时 j 为6，且字符D对应的next 值为2，所以向右移动的位数为：j - next[j] = 6 - 2 =4 位
- ②向右移动4位后，C再次失配，向右移动：j - next[j] = 2 - 0 = 2 位
- ③移动两位之后，A 对应着空格导致不匹配，再次后移1 位
- ④D处失配，向右移动 j - next[j] = 6 - 2 = 4 位
- ⑤匹配成功，过程结束。
匹配过程一模一样。也从侧面佐证了，next 数组确实是只要将各个最大前缀后缀的公共元素的长度值右移一位，且把初值赋为-1 即可。
基于《最大长度表》与基于《next 数组》等价
其实，利用next 数组进行匹配失配时，模式串向右移动 j - next [ j ] 位，等价于已匹配字符数 - 失配字符的上一位字符所对应的最大长度值。为什么呢？
- j 从0开始计数，那么当数到失配字符时，j 的数值就是已匹配的字符数；
- 由于next 数组是由最大长度值表整体向右移动一位（且初值赋为-1）得到的，那么失配字符的上一位字符所对应的最大长度值，即为当前失配字符的next 值。
那为何本文不直接利用next 数组进行匹配呢？因为next 数组不好求，而一个字符串的前缀后缀的公共元素的最大长度值很容易求，例如若给定字符串“abab”，要你求其next 数组，则乍一看，无从求起，而要你求其前缀后缀公共元素的最大长度，则很容易得出是：0 0 1 2，如下表格所示：
然后这4个数字 全部整体右移一位，且初值赋为-1，即得到其next 数组：-1 0 0 1。
next 数组的理解
next 负责把模式串向前移动，且当第j位不匹配的时候，用第next[j]位和主串匹配，就像打了张“表”。此外，next 也可以看作有限状态自动机的状态，在已经读了多少字符的情况下，失配后，前面读的若干个字符是有用的。
btw，如果你觉得上述手绘图比较丑的话，可以看下微博上一热心朋友@龚陆安 用Latex和TikZ 帮忙画的图：。完。
参考文献
- 本文第一张朴素算法匹配的图来自《算法导论》的第十二章：字符串匹配；
- 本文中字符串
http://blog.sina.com.cn/s/blog_6a2787d40102uxsm.html