谈一谈KMP算法

写这篇博客的主要原因是今天上课后对kmp算法还有些许疑问，课后上网一查资料才发现，贵校有时对专业课真的很不负责。

同时也算是开了一个新坑吧，我会不定时的补充一些其他算法的新资料。

贵校教材是1997年出版的，有很多错误或者是很老的算法，但是贵校教材还把他列为必考内容，这对于一个SE学生来说有很大的影响。

就那kmp算法来言贵校的教材把next和nextval并列而谈，而现在的主流kmp算法只有一个next数组，其算法为贵校的nextval算法的优化。

这里我来简单的谈一谈kmp算法。

The Partial Match Table

以下这一部分是对http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/这篇博客的简单翻译以及个人的理解

kmp算法最主要的部分就是partial match table（这里笔者暂时没有找到合适的语言来翻译这个词组，怕片面的解释而导致大家理解出现错误）。最主要的障碍在我和理解kmp算法就是我们不能真正抓住partial match table其真正的含义。我现在将尝试解释一下这个词组的真正含义。

这里有个针对于模式串“abababca”的partial match table

这里我有8个字符的模式串（当然，接下来的例子都以这个字符为例），所以得到的partial match table就会有8个数字。如果我看向第8个字符，对我来说我看的就是整个模式串（”abababca”）。如果我看向表中的第7个字符，我只感兴趣的是模式串中的前七个字符，即(“abababc”)，第八个字符’a’就被忽视了。同理，如果我看向模式串中的第六个字符…

现在为了具体说一说kmp算法，我们需要理解proper prefixes（合适的前缀？）和 proper suffixes （合适的后缀？）。

然后笔者想了一想下文还是用英文代替这两个名词吧。。。

Proper prefix:在整个字符串中，从开始到最后一个字符前的所有子串。例如：”Snape”的所有proper prefixes为”S”,”Sn”,”Sna”,”Snap”

Proper suffix:在整个字符串中，从最后到第一个字符的所有子串。例如：”Hargrid”的所有proper suffixes为”agrid”,”grid”,”rid”,”id”,”d”

有了上诉的概念，这样我就可以给出value的定义了：

The length of the longest proper prefix in the (sub)pattern that matches a proper suffix in the same (sub)pattern.

来解释一下我所指的意思。现在我们看向第三个字符，正如前文所说，我们只关注从开始起到第三个字符(“aba”)。在aba里有两个proper prefixes分别为“a”和“ab”；有两个proper suffixes分别为“a”和“ba”。其中“ab”和“ba”并不匹配，但是“a”和“a”是相匹配的。所以，此时的value就是最长的相匹配的字符数，这里为1。

现在让我们尝试一下第四个字符。同样，我们只看前四个字符(“abab”)。我们有proper prefixes“a”“ab”“aba”和proper suffixes”b””ab””bab”。这次，“ab”是共有的，并且有两个字符的长度，所以此时的value为2。

同理我们来看第五个字符。我们得到相匹配的字符串有两个，一个是“aba”，另一个是“a”。因为aba的长度大于a，所以这里的value返回3.

然而我们在看向第7个（即倒数第二个）的字符时，我们可以发现没有一个相对应的proper prefixes和proper suffixes是匹配的。所以我们这里的value返回0.

最后我们来看第8个字符，这里包含了整个字符串。因为第一个字符和最后一个字符都是a，所以此时的value至少返回1.这里我们不难发现，从2开始，所有的proper suffixes都有a和c这两个字符，但是proper prefixes中只有最后一个“abababc”中含有字符c，显然易见，其value值返回1.

当然写到这里相信大家对value的值已经有了一个初步的理解了，下面就来详细谈谈kmp算法的使用及其优化。

kmp算法的定义

Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP 算法”，常用于在一个文本串 S 内查找一个模式串 P 的出现位置。这个算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，故取这三人的姓氏命名此算法。（膜一下三位dalao）

下面直接给出算法的基础流程，当然我会在下文做详细的讲解。

假设现在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置
如果 j = -1，或者当前字符匹配成功（即 S[i] == P[j]），都令 i++，j++，继续匹配下一个字符；
如果 j != -1，且当前字符匹配失败（即 S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串 P 相对于文本串 S 向右移动了 j - next [j] 位。
换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的 next 值（next 数组的求解会在下文详细阐述），即移动的实际位数为：j - next[j]，且此值大于等于1。

此也意味着在某个字符失配时，该字符对应的 next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果 next [j] 等于 0 或 -1，则跳到模式串的开头字符，若 next [j] = k 且 k > 0，代表下次匹配跳到 j 之前的某个字符，而不是跳到开头，且具体跳过了 k 个字符。

int KmpSearch(char* s, char* p) {  
    int i = 0;  
    int j = 0;  
    int sLen = strlen(s);  
    int pLen = strlen(p);  
    while (i < sLen && j < pLen) {  
        //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++      
        if (j == -1 || s[i] == p[j]) {  
            i++;  
            j++;  
        }  
        else {  
            //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]      
            //next[j]即为j所对应的next值        
            j = next[j];  
        }  
    }  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  
}

根据The Partial Match Table 求next数组

由上文，我们可以推出，字符串“ABCDABD”各个前缀后缀的最大公共元素长度分别为

1 2	String: A \| B \| C \| D \| A \| B \| D Value: 0 \| 0 \| 0 \| 0 \| 1 \| 2 \| 0

而且，根据这个表可以得出下述结论

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

上文利用这个表和结论进行匹配时，我们发现，当匹配到一个字符失配时，其实没必要考虑当前失配的字符，更何况我们每次失配时，都是看的失配字符的上一位字符对应的最大长度值。如此，便引出了 next 数组。

给定字符串“ABCDABD”，可求得它的 next 数组如下：

1
2
3

String:	 A | B | C | D | A | B | D	
Value:   0 | 0 | 0 | 0 | 1 | 2 | 0
Next:	-1 | 0 | 0 | 0 | 0 | 1 | 2

(这里可能会与学校所讲的不一样，但是请耐心向下看)

把 next 数组跟之前求得的最大长度表对比后，不难发现，next 数组相当于“最大长度值” 整体向右移动一位，然后初始值赋为 -1。意识到了这一点，你会惊呼原来 next 数组的求解竟然如此简单：就是找最大对称长度的前缀后缀，然后整体右移一位，初值赋为 -1（当然，你也可以直接计算某个字符对应的 next 值，就是看这个字符之前的字符串中有多大长度的相同前缀后缀）。

根据最大长度表求出了 next 数组后，从而有

失配时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值

而后，你会发现，无论是基于The Partial Match Table的匹配，还是基于 next 数组的匹配，两者得出来的向右移动的位数是一样的。为什么呢？因为：

根据The Partial Match Table，失配时，模式串向右移动的位数 = 已经匹配的字符数 - 失配字符的上一位字符的最大长度值
而根据《next 数组》，失配时，模式串向右移动的位数 = 失配字符的位置 - 失配字符对应的 next 值
其中，从 0 开始计数时，失配字符的位置 = 已经匹配的字符数（失配字符不计数），而失配字符对应的 next 值 = 失配字符的上一位字符的最大长度值，两相比较，结果必然完全一致。

所以，你可以把The Partial Match Table看做是 next 数组的雏形，甚至就把它当做 next 数组也是可以的，区别不过是怎么用的问题。

通过代码递推计算 next 数组

接下来，咱们来写代码求下 next 数组

基于之前的理解，可知计算 next 数组的方法可以采用递推：

如果对于值 k，已有 p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，相当于 next[j] = k。 此意味着什么呢？究其本质，next[j] = k 代表 p[j] 之前的模式串子串中，有长度为 k 的相同前缀和后缀。有了这个 next 数组，在 KMP 匹配中，当模式串中 j 处的字符失配时，下一步用 next[j] 处的字符继续跟文本串匹配，相当于模式串向右移动 j - next[j] 位。

举个例子，如下图，根据模式串“ABCDABD”的 next 数组可知失配位置的字符 D 对应的 next 值为 2，代表字符 D 前有长度为 2 的相同前缀和后缀（这个相同的前缀后缀即为“AB”），失配后，模式串需要向右移动 j - next [j] = 6 - 2 =4 位。

向右移动 4 位后，模式串中的字符 C 继续跟文本串匹配。

下面的问题是：已知 next [0, …, j]，如何求出 next [j + 1] 呢？

对于 P 的前 j+1 个序列字符：

1.若p[k] == p[j]，则 next[j + 1 ] = next [j] + 1 = k + 1；

2.若p[k ] ≠ p[j]，如果此时 p[ next[k] ] == p[j ]，则 next[ j + 1 ] = next[k] + 1，否则继续递归前缀索引 k = next[k]，而后重复此过程。相当于在字符 p[j+1] 之前不存在长度为 k+1 的前缀”p0 p1, …, pk-1 pk”跟后缀“pj-k pj-k+1, …, pj-1 pj”相等，那么是否可能存在另一个值 t+1 < k+1，使得长度更小的前缀 “p0 p1, …, pt-1 pt” 等于长度更小的后缀 “pj-t pj-t+1, …, pj-1 pj” 呢？如果存在，那么这个 t+1 便是 next[ j+1] 的值，此相当于利用已经求得的 next 数组（next [0, …, k, …, j]）进行 P 串前缀跟 P 串后缀的匹配。

一般的文章或教材可能就此一笔带过，但大部分的初学者可能还是不能很好的理解上述求解 next 数组的原理，故接下来，我再来着重说明下。

如下图所示，假定给定模式串 ABCDABCE，且已知 next [j] = k（相当于“p0 pk-1” = “pj-k pj-1” = AB，可以看出 k 为 2），现要求 next [j + 1] 等于多少？因为 pk = pj = C，所以 next[j + 1] = next[j] + 1 = k + 1（可以看出 next[j + 1] = 3）。代表字符 E 前的模式串中，有长度 k+1 的相同前缀后缀。

但如果 pk != pj 呢？说明“p0 pk-1 pk” ≠ “pj-k pj-1 pj”。换言之，当 pk != pj 后，字符 E 前有多大长度的相同前缀后缀呢？很明显，因为 C 不同于 D，所以 ABC 跟 ABD 不相同，即字符 E 前的模式串没有长度为 k+1 的相同前缀后缀，也就不能再简单的令：next[j + 1] = next[j] + 1 。所以，咱们只能去寻找长度更短一点的相同前缀后缀。

结合上图来讲，若能在前缀“ p0 pk-1 pk ” 中不断的递归前缀索引 k = next [k]，找到一个字符 pk’ 也为 D，代表 pk’ = pj，且满足 p0 pk’-1 pk’ = pj-k’ pj-1 pj，则最大相同的前缀后缀长度为 k’ + 1，从而 next [j + 1] = k’ + 1 = next [k’ ] + 1。否则前缀中没有 D，则代表没有相同的前缀后缀，next [j + 1] = 0。

那为何递归前缀索引k = next[k]，就能找到长度更短的相同前缀后缀呢？

这又归根到 next 数组的含义。我们拿前缀 p0 pk-1 pk 去跟后缀 pj-k pj-1 pj 匹配，如果 pk 跟 pj 失配，下一步就是用 p[next[k]] 去跟 pj 继续匹配，如果 p[ next[k] ]跟 pj 还是不匹配，则需要寻找长度更短的相同前缀后缀，即下一步用 p[ next[ next[k] ] ] 去跟 pj 匹配。此过程相当于模式串的自我匹配，所以不断的递归 k = next[k]，直到要么找到长度更短的相同前缀后缀，要么没有长度更短的相同前缀后缀。如下图所示：

所以，因最终在前缀 ABC 中没有找到 D，故 E 的 next 值为 0：

1
2
3

模式串的后缀：ABDE
模式串的前缀：ABC
前缀右移两位：  ABC

读到此，有的读者可能又有疑问了，那能否举一个能在前缀中找到字符 D 的例子呢？OK，咱们便来看一个能在前缀中找到字符 D 的例子，如下图所示：

给定模式串 DABCDABDE，我们很顺利的求得字符 D 之前的“DABCDAB”的各个子串的最长相同前缀后缀的长度分别为 0 0 0 0 1 2 3，但当遍历到字符 D，要求包括 D 在内的“DABCDABD”最长相同前缀后缀时，我们发现 pj 处的字符 D 跟 pk 处的字符 C 不一样，换言之，前缀 DABC 的最后一个字符 C 跟后缀 DABD 的最后一个字符 D 不相同，所以不存在长度为 4 的相同前缀后缀。

怎么办呢？既然没有长度为 4 的相同前缀后缀，咱们可以寻找长度短点的相同前缀后缀，最终，因在 p0 处发现也有个字符 D，p0 = pj，所以 p[j] 对应的长度值为 1，相当于 E 对应的 next 值为 1（即字符 E 之前的字符串“DABCDABD”中有长度为 1 的相同前缀和后缀）。

综上，可以通过递推求得 next 数组，代码如下所示：

void GetNext(char* p,int next[]) {  
    int pLen = strlen(p);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1) {  
        //p[k]表示前缀，p[j]表示后缀  
        if (k == -1 || p[j] == p[k]) {  
            ++k;  
            ++j;  
            next[j] = k;  
        }  
        else {  
            k = next[k];  
        }  
    }  
}

用代码重新计算下“ABCDABD”的 next 数组，以验证之前通过“最长相同前缀后缀长度值右移一位，然后初值赋为 -1” 得到的 next 数组是否正确，计算结果如下表格所示：

从上述表格可以看出，无论是之前通过“最长相同前缀后缀长度值右移一位，然后初值赋为 -1” 得到的 next 数组，还是之后通过代码递推计算求得的 next 数组，结果是完全一致的。

基于next 数组匹配

下面，我们来基于 next 数组进行匹配。

1 2	String: A \| B \| C \| D \| A \| B \| D Next: -1 \| 0 \| 0 \| 0 \| 0 \| 1 \| 2

还是给定文本串“BBC ABCDAB ABCDABCDABDE”，和模式串“ABCDABD”，现在要拿模式串去跟文本串匹配，如下图所示：

在正式匹配之前，让我们来再次回顾下上文所述的 KMP 算法的匹配流程：

“假设现在文本串S匹配到 i 位置，模式串 P 匹配到 j 位置
如果 j = -1，或者当前字符匹配成功（即 S[i] == P[j]），都令 i++，j++，继续匹配下一个字符；
如果 j != -1，且当前字符匹配失败（即 S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串 P 相对于文本串 S 向右移动了 j - next [j] 位。
换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的 next 值，即移动的实际位数为：j - next[j]，且此值大于等于1。”

1.最开始匹配时

P[0] 跟 S[0] 匹配失败

　　所以执行“如果 j != -1，且当前字符匹配失败（即 S[i] != P[j]），则令 i 不变，j = next[j]”，所以 j = -1，故转而执行“如果 j = -1，或者当前字符匹配成功（即 S[i] == P[j]），都令 i++，j++”，得到i = 1，j = 0，即 P[0] 继续跟 S[1] 匹配。
　　
P[0] 跟 S[1] 又失配，j 再次等于 -1，i、j 继续自增，从而 P[0] 跟 S[2] 匹配。

P[0] 跟 S[2] 失配后，P[0] 又跟 S[3] 匹配。

P[0] 跟 S[3] 再失配，直到 P[0] 跟 S[4] 匹配成功，开始执行此条指令的后半段：“如果 j = -1，或者当前字符匹配成功（即 S[i] == P[j]），都令 i++，j++”。

2.P[1] 跟 S[5] 匹配成功，P[2] 跟 S[6] 也匹配成功, …，直到当匹配到 P[6] 处的字符 D 时失配（即 S[10] != P[6]），由于 P[6] 处的 D 对应的 next 值为 2，所以下一步用 P[2] 处的字符 C 继续跟 S[10] 匹配，相当于向右移动：j - next[j] = 6 - 2 =4 位。

3.向右移动 4 位后，P[2] 处的 C 再次失配，由于 C 对应的 next 值为 0，所以下一步用 P[0] 处的字符继续跟 S[10] 匹配，相当于向右移动：j - next[j] = 2 - 0 = 2 位。

4.移动两位之后，A 跟空格不匹配，模式串后移 1 位。

5.P[6] 处的 D 再次失配，因为 P[6] 对应的 next 值为 2，故下一步用 P[2] 继续跟文本串匹配，相当于模式串向右移动 j - next[j] = 6 - 2 = 4 位。

6.匹配成功，过程结束。

匹配过程一模一样。也从侧面佐证了，next 数组确实是只要将各个最大前缀后缀的公共元素的长度值右移一位，且把初值赋为 -1 即可。

基于Partial Match Table与基于next 数组等价

我们已经知道，利用 next 数组进行匹配失配时，模式串向右移动 j - next [ j ] 位，等价于已匹配字符数 - 失配字符的上一位字符所对应的最大长度值。原因是:

1.j 从 0 开始计数，那么当数到失配字符时，j 的数值就是已匹配的字符数；

2.由于 next 数组是由最大长度值表整体向右移动一位（且初值赋为 -1）得到的，那么失配字符的上一位字符所对应的最大长度值，即为当前失配字符的 next 值。

但为何本文不直接利用 next 数组进行匹配呢？因为 next 数组不好求，而一个字符串的前缀后缀的公共元素的最大长度值很容易求。例如若给定模式串“ababa”，要你快速口算出其 next 数组，乍一看，每次求对应字符的 next 值时，还得把该字符排除之外，然后看该字符之前的字符串中有最大长度为多大的相同前缀后缀，此过程不够直接。而如果让你求其前缀后缀公共元素的最大长度，则很容易直接得出结果：0 0 1 2 3，如下表格所示：

然后这 5 个数字全部整体右移一位，且初值赋为 -1，即得到其 next 数组：-1 0 0 1 2。

Next 数组的优化

行文至此，咱们全面了解了KMP算法的原理、流程、流程之间的内在逻辑联系，以及 next 数组的简单求解（Partial Match Table整体右移一位，然后初值赋为 -1）和代码求解，最后基于next 数组的匹配，看似洋洋洒洒，清晰透彻，但以上忽略了一个小问题。

比如，如果用之前的 next 数组方法求模式串“abab”的 next 数组，可得其 next 数组为-1 0 0 1（0 0 1 2整体右移一位，初值赋为 -1），当它跟下图中的文本串去匹配的时候，发现 b 跟 c 失配，于是模式串右移 j - next[j] = 3 - 1 =2 位。

右移 2 位后，b 又跟 c 失配。事实上，因为在上一步的匹配中，已经得知 p[3] = b，与 s[3] = c 失配，而右移两位之后，让 p[ next[3] ] = p[1] = b 再跟 s[3] 匹配时，必然失配。问题出在哪呢？

问题出在不该出现 p[j] = p[ next[j] ]。为什么呢？理由是：当 p[j] != s[i] 时，下次匹配必然是 p[ next [j]] 跟 s[i] 匹配，如果 p[j] = p[ next[j] ]，必然导致后一步匹配失败（因为 p[j] 已经跟 s[i] 失配，然后你还用跟 p[j] 等同的值 p[next[j]] 去跟 s[i] 匹配，很显然，必然失配），所以不能允许 p[j] = p[ next[j ]]。如果出现了 p[j] = p[ next[j] ] 咋办呢？如果出现了，则需要再次递归，即令 next[j] = next[ next[j] ]。

所以，咱们得修改下求 next 数组的代码。

//优化过后的next 数组求法  
void GetNextval(char* p, int next[]) {  
    int pLen = strlen(p);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1) {  
        //p[k]表示前缀，p[j]表示后缀    
        if (k == -1 || p[j] == p[k]) {  
            ++j;  
            ++k;  
            //较之前next数组求法，改动在下面4行  
            if (p[j] != p[k])  
                next[j] = k;   //之前只有这一行  
            else  
                //因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]  
                next[j] = next[k];  
        }  
        else {  
            k = next[k];  
        }  
    }  
}

利用优化过后的 next 数组求法，可知模式串“abab”的新 next 数组为：-1 0 -1 0。可能有些读者会问：原始next 数组是前缀后缀最长公共元素长度值右移一位，然后初值赋为 -1 而得，那么优化后的 next 数组如何快速心算出呢？实际上，只要求出了原始 next 数组，便可以根据原始 next 数组快速求出优化后的 next 数组。还是以 abab 为例，如下表格所示：

只要出现了 p[next[j]] = p[j] 的情况，则把 next[j] 的值再次递归。例如在求模式串“abab”的第 2 个 a 的 next 值时，如果是未优化的 next 值的话，第 2 个 a 对应的 next 值为 0，相当于第 2 个 a 失配时，下一步匹配模式串会用 p[0] 处的 a 再次跟文本串匹配，必然失配。所以求第 2 个 a 的 next 值时，需要再次递归：next[2] = next[ next[2] ] = next[0] = -1（此后，根据优化后的新 next 值可知，第 2 个 a 失配时，执行“如果 j = -1，或者当前字符匹配成功（即 S[i] == P[j]），都令 i++，j++，继续匹配下一个字符”），同理，第 2 个 b 对应的 next 值为 0。

对于优化后的 next 数组可以发现一点：如果模式串的后缀跟前缀相同，那么它们的 next 值也是相同的，例如模式串 abcabc，它的前缀后缀都是 abc，其优化后的 next 数组为：-1 0 0 -1 0 0，前缀后缀 abc 的 next 值都为 -1 0 0。

然后引用下之前 KMP 代码：

int KmpSearch(char* s, char* p) {  
    int i = 0;  
    int j = 0;  
    int sLen = strlen(s);  
    int pLen = strlen(p);  
    while (i < sLen && j < pLen) {  
        //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++      
        if (j == -1 || s[i] == p[j]) {  
            i++;  
            j++;  
        }  
        else {  
            //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]      
            //next[j]即为j所对应的next值        
            j = next[j];  
        }  
    }  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  
}

接下来，咱们继续拿之前的例子说明，整个匹配过程如下：
1.S[3] 与 P[3] 匹配失败。

2.S[3] 保持不变，P 的下一个匹配位置是 P[next[3]]，而 next[3]=0，所以 P[next[3]]=P[0] 与 S[3] 匹配。

3.由于上一步骤中 P[0] 与 S[3] 还是不匹配。此时 i=3，j=next [0]=-1，由于满足条件 j==-1，所以执行“++i, ++j”，即主串指针下移一个位置，P[0] 与 S[4] 开始匹配。最后 j==pLen，跳出循环，输出结果 i - j = 4（即模式串第一次在文本串中出现的位置），匹配成功，算法结束。

KMP 的时间复杂度分析

相信大部分读者读完上文之后，已经发觉其实理解 KMP 非常容易，无非是循序渐进把握好下面几点：

如果模式串中存在相同前缀和后缀，即 pj-k pj-k+1, …, pj-1 = p0 p1, …, pk-1，那么在 pj 跟 si 失配后，让模式串的前缀 p0 p1…pk-1 对应着文本串 si-k si-k+1…si-1，而后让 pk 跟 si 继续匹配。

之前本应是 pj 跟 si 匹配，结果失配了，失配后，令 pk 跟 si 匹配，相当于 j 变成了 k，模式串向右移动 j - k 位。

因为 k 的值是可变的，所以我们用 next[j] 表示j处字符失配后，下一次匹配模式串应该跳到的位置。换言之，失配前是 j，pj 跟 si 失配时，用 p[ next[j] ]继续跟 si 匹配，相当于 j 变成了 next[j]，所以，j = next[j]，等价于把模式串向右移动 j - next [j] 位。

而 next[j] 应该等于多少呢？ next[j] 的值由 j 之前的模式串子串中有多大长度的相同前缀后缀所决定，如果 j 之前的模式串子串中（不含 j）有最大长度为k的相同前缀后缀，那么 next [j] = k。

如图所示：

接下来，咱们来分析下 KMP 的时间复杂度。分析之前，先来回顾下 KMP 匹配算法的流程：

假设现在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置
如果 j = -1，或者当前字符匹配成功（即 S[i] == P[j]），都令 i++，j++，继续匹配下一个字符；
如果 j != -1，且当前字符匹配失败（即 S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串 P 相对于文本串 S 向右移动了 j - next [j] 位。
换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的 next 值（next 数组的求解会在下文详细阐述），即移动的实际位数为：j - next[j]，且此值大于等于1。

我们发现如果某个字符匹配成功，模式串首字符的位置保持不动，仅仅是 i++、j++；如果匹配失配，i 不变（即 i 不回溯），模式串会跳过匹配过的 next [j] 个字符。整个算法最坏的情况是，当模式串首字符位于 i - j 的位置时才匹配成功，算法结束。

所以，如果文本串的长度为 n，模式串的长度为 m，那么匹配过程的时间复杂度为 O(n)，算上计算 next 的 O(m) 时间，KMP 的整体时间复杂度为 O(m + n)。

扩展1：BM算法

KMP的匹配是从模式串的开头开始匹配的，而1977年，德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了一种新的字符串匹配算法：Boyer-Moore算法，简称BM算法。该算法从模式串的尾部开始匹配，且拥有在最坏情况下O(N)的时间复杂度。在实践中，比KMP算法的实际效能高。

BM算法定义了两个规则：

1.坏字符规则：当文本串中的某个字符跟模式串的某个字符不匹配时，我们称文本串中的这个失配字符为坏字符，此时模式串需要向右移动，移动的位数 = 坏字符在模式串中的位置 - 坏字符在模式串中最右出现的位置。此外，如果”坏字符”不包含在模式串之中，则最右出现位置为-1。

2.好后缀规则：当字符失配时，后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置，且如果好后缀在模式串中没有再次出现，则为-1。

下面举例说明BM算法。例如，给定文本串“HERE IS A SIMPLE EXAMPLE”，和模式串“EXAMPLE”，现要查找模式串是否在文本串中，如果存在，返回模式串在文本串中的位置。

首先，”文本串”与”模式串”头部对齐，从尾部开始比较。”S”与”E”不匹配。这时，”S”就被称为”坏字符”（bad character），即不匹配的字符，它对应着模式串的第6位。且”S”不包含在模式串”EXAMPLE”之中（相当于最右出现位置是-1），这意味着可以把模式串后移6-(-1)=7位，从而直接移到”S”的后一位。

依然从尾部开始比较，发现”P”与”E”不匹配，所以”P”是”坏字符”。但是，”P”包含在模式串”EXAMPLE”之中。因为“P”这个“坏字符”对应着模式串的第6位（从0开始编号），且在模式串中的最右出现位置为4，所以，将模式串后移6-4=2位，两个”P”对齐。

依次比较，得到 “MPLE”匹配，称为”好后缀”（good suffix），即所有尾部匹配的字符串。注意，”MPLE”、”PLE”、”LE”、”E”都是好后缀。

发现“I”与“A”不匹配：“I”是坏字符。如果是根据坏字符规则，此时模式串应该后移2-(-1)=3位。问题是，有没有更优的移法？

更优的移法是利用好后缀规则：当字符失配时，后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串中上一次出现的位置，且如果好后缀在模式串中没有再次出现，则为-1。

所有的“好后缀”（MPLE、PLE、LE、E）之中，只有“E”在“EXAMPLE”的头部出现，所以后移6-0=6位。

可以看出，“坏字符规则”只能移3位，“好后缀规则”可以移6位。每次后移这两个规则之中的较大值。这两个规则的移动位数，只与模式串有关，与原文本串无关。

继续从尾部开始比较，“P”与“E”不匹配，因此“P”是“坏字符”，根据“坏字符规则”，后移 6 - 4 = 2位。因为是最后一位就失配，尚未获得好后缀。

BM算法不仅效率高，而且构思巧妙，容易理解

扩展2：Sunday算法

上文中，我们已经介绍了KMP算法和BM算法，这两个算法在最坏情况下均具有线性的查找时间。但实际上，KMP算法并不比最简单的c库函数strstr()快多少，而BM算法虽然通常比KMP算法快，但BM算法也还不是现有字符串查找算法中最快的算法，本文最后再介绍一种比BM算法更快的查找算法即Sunday算法。

Sunday算法由Daniel M.Sunday在1990年提出，它的思想跟BM算法很相似：

只不过Sunday算法是从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。
如果该字符没有在模式串中出现则直接跳过，即移动位数 = 匹配串长度 + 1；
否则，其移动位数 = 模式串中最右端的该字符到末尾的距离+1。

下面举个例子说明下Sunday算法。假定现在要在文本串”substring searching algorithm”中查找模式串”search”。

刚开始时，把模式串与文本串左边对齐：

1
2
3

substring searching algorithm
search
^

结果发现在第2个字符处发现不匹配，不匹配时关注文本串中参加匹配的最末位字符的下一位字符，即标粗的字符 i，因为模式串search中并不存在i，所以模式串直接跳过一大片，向右移动位数 = 匹配串长度 + 1 = 6 + 1 = 7，从 i 之后的那个字符（即字符n）开始下一步的匹配，如下

1
2
3

substring searching algorithm
　　　 	  search
          ^

结果第一个字符就不匹配，再看文本串中参加匹配的最末位字符的下一位字符，是’r’，它出现在模式串中的倒数第3位，于是把模式串向右移动3位（r 到模式串末尾的距离 + 1 = 2 + 1 =3），使两个’r’对齐，如下

1
2
3

substring  searching algorithm
　　　　    search
              ^

匹配成功。

回顾整个过程，我们只移动了两次模式串就找到了匹配位置，缘于Sunday算法每一步的移动量都比较大，效率很高

感谢

http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html

http://www.cnblogs.com/yjiyjige/p/3263858.html

http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/

SaberDa的幻想乡

C++/ JS　　|　　呐呐呐　　|　　gli97@gwmail.gwu.edu　　|　　没有什么胜利可言挺住就意味着一切