KMP 算法是计算机字符串匹配的常规算法。wiki
本篇文章借助简单示例，用通俗易懂的方式描述对 KMP 算法的理解。
匹配值表
对于 KMP 来说，“匹配值表”是很关键的。下面我们从简单示例出发描述匹配值表是如何产生的，以便理解。
现在 我们需要查找的字符串是 “ABABABCA”。
在描述“匹配值表“之前，我们需要简短的介绍下前缀和后缀的概念:
前缀：从 0 位，依次截取 1 到(len - 1)长度字符串的集合
后缀：从 len - 1 位反序，依次截取 1 到(len - 1)长度字符串的集合
| 字符串 | 前缀集合 | 后缀集合 | 前缀后缀交集 |
|---|---|---|---|
| "A" | [] | [] | [] |
| "AB" | [A] | [B] | [] |
| "ABA" | [A,AB] | [A, BA] | [A] |
| "ABAB" | [A, AB, ABA] | [B, AB, BAB] | [AB] |
| "ABABA" | [A, AB, ABA, ABAB] | [A, BA, ABA, BABA] | [A, ABA] |
| "ABABAB" | [A, AB, ABA, ABAB, ABABA] | [B, AB, BAB, ABAB, BABAB] | [AB, ABAB] |
| "ABABABC" | [A, AB, ABA, ABAB, ABABA, ABABAB] | [C, BC, ABC, BABC, ABABC, BABABC] | [] |
| "ABABABCA" | [A, AB, ABA, ABAB, ABABA, ABABAB, ABABABC] | [A, CA, BCA, ABCA, BABCA, ABABCA, BABABCA] | [A] |
从上表，如果耐心看，完全可以理解前缀和后缀的概念。
那么“匹配值”又是指什么呢？
“匹配值”是指前缀和后缀集合，最长共有元素的长度，即交集中最长元素的长度
那么不难从上表中得出每一位(index)字符对应“匹配值(value)”:
char: | A | B | A | B | A | B | C | A |
index:| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
value:| 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
匹配值表的使用
我们可以根据匹配值表来加速查找匹配的过程。
下面还是举例说明问题：
在字符串"BACBABABAABCBABABABCA"(text)中查找上文中的字符串"ABABABCA"(pattern)，
下文中对两个字符串的代称为括号之内的单词。
从 text 第一位开始匹配，第一次匹配成功是这样：
BACBABABAABCBABABABCA
|
ABABABCA
那么开始往后匹配，发现 text 的第二位"C"和 pattern 的第二位"B"不匹配，
所以当前部分匹配长度为1(只有一个A)，并且根据上文的匹配值表得到，当前的匹配值为 0。
移动位数 = 已匹配字符长度 - 对应位的匹配值
即 移动位数 = 1 - 0，所以我们继续向后移一位进行匹配。
再一次匹配成功的情形：
BACBABABAABCBABABABCA
|||||
ABABABCA
此时，text 中的"A"与 pattern 中的 "B" 不匹配，如果不按照算法，肯定是继续后移一位进行匹配。
如果根据上述计算公式：
移动位数 = "ABABA".length - pattern[4]的匹配值
即 5 - 3 = 2
所以我们可以一次后移两位：
BACBABABAABCBABABABCA
xx|||
ABABABCA
又不匹配了，此时应该后移
"ABA".length - pattern[2]的匹配值
即 3 - 1 = 2
继续后移两位：
BACBABABAABCBABABABCA
xx|
ABABABCA
继续后移
"A".length - pattern[0]的匹配值
即 1 - 0 = 1
后移一位：
BACBABABAABCBABABABCA
x||
ABABABCA
继续后移
"AB".length - pattern[1]的匹配值
即 2 - 0 = 2
后移两位：
BACBABABAABCBABABABCA
xx|
ABABABCA
第一位都不匹配，我们继续往后移动直到匹配成功
BACBABABAABCBABABABCA
||||||||
ABABABCA
移动几次之后(step=1)，找到了最终匹配结果。
参考：
http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
