从头到尾彻底理解KMP(转)

引言

KMP原文最初写于2年多前的2011年12月，因当时初次接触KMP，思路混乱导致写也写得非常混乱，如此，留言也是骂声一片。所以一直想找机会重新写下KMP，但苦于一直以来对KMP的理解始终不够，故才迟迟没有修改本文。

然近期因在北京开了个算法班，专门讲解数据结构、面试、算法，才再次仔细回顾了这个KMP，在综合了一些网友的理解、以及跟我一起讲算法的两位讲师朋友曹博、邹博的理解之后，写了9张PPT，发在微博上。一不做二不休，索性将PPT上的内容整理到了本文之中。

KMP本身不复杂，但网上大部分的文章（包括本文的2011年版本）把它讲混乱了。下面，咱们从朴素匹配算法讲起，一步步从字符串的前缀后缀引入next数组，最后利用next 数组进行匹配，希望让大家对KMP有一个清晰的了解。

咱们先来看朴素匹配算法。假设现在原始串S串匹配到 i 位置，模式串T串匹配到 j 位置

换言之，只要模式串匹配失败，那就往右边移动一位，简单直接，也干脆暴力。

假定原始串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”，那么它的各个前缀后缀的公共元素的最大长度值如下表格所示：

接下来，分别具体阐述这3个步骤。

如果给定的模式串是：“ABCDABD”，那么其各个前缀后缀字符串分别如下表格所示：

也就是说，原字符串对应的各个前缀后缀的公共元素的最大长度表为（下简称最大长度表）：

因为模式串中首尾可能会有重复的字符，故可得出下述结论：

失配时，模式串向右移动的位数为：已匹配字符数 - 失配字符的上一位字符所对应的最大长度值

下面，咱们就结合之前的最大长度表和上述结论，进行字符串的匹配。如果给定原始串“BBC ABCDAB ABCDABCDABDE”，和模式串“ABCDABD”，现在要拿模式串去跟原始串匹配，如下图所示：

①当模式串最后一个字符D跟原始串匹配时失配，显而易见，模式串需要向右移动。但向右移动多少位呢？
- 如果利用最原始的朴素匹配算法，那么把模式串不断的向右移动一位，直到全部字符实现匹配；
- 事实上，因为此时已经匹配的字符数为6个（ABCDAB），然后根据《最大长度表》可得字符B对应的长度值为2，所以根据之前的结论，可知需要向右移动6 - 2 = 4 位。