在进入正题前，我们首先来回顾一下暴力匹配算法。总计来说，就是逐个字符匹配，匹配成功后，再匹配下一个字符，直到所有字符匹配成功，若在中间有任意一个字符匹配失败，则回溯至从第二个字符开始进行新的匹配。
而KMP算法则是根据一些已知的信息，跳过一些没有必要的匹配，从而达到更高的匹配效率。举例来说，假设我们有这样的一个主串A："AMKLCOMSAMKLCOMD"
和这样的一个子串B：
"AMKLCOMD"
由第一次的匹配算法可知"AMKLCOMS"后面的"AMKLCOMS"没有和"A"相等的字符，所以这后面的匹配其实是都可以省略的。
KMP算法通过一个“有用信息”可以知道目标串中下一个字符是否有必要被检测，这个“有用信息”就是用所谓的“前缀函数（一般数据结构书中的next函数）”来存储的。这个函数能够反映出现失配情况时，系统应该跳过多少无用字符（也即模式串应该向右滑动多长距离）而进行下一次检测，在上例中，这个距离为6。很明显，我们现在是通过肉眼看出来的，但是这并不是我们最终的目的，我们最终是要通过程序来实现这样的跳过匹配。我们先来解释几个名词，前缀，后缀，最大长度，next数组。假设我们现在有一个字符串："CDEFCD"一.前缀，后缀| 子串 | 前缀 | 后缀 | 最大公共长度 |
|---|---|---|---|
| C | null | null | 0 |
| CD | C | D | 0 |
| CDE | C, CD | E, DE | 0 |
| CDEF | C, CD, CDE | F, EF, DEF | 0 |
| CDEFC | C, CD, CDE, CDEF | C, FC, EFC, DEFC | 1 |
| CDEFCD | C, CD, CDE, CDEF, CDEFC | D, CD, FCD, EFCD, DEFCD | 2 |
最大长度表
| C | D | E | F | C | D |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 2 |
二.next数组
假设现在有主串ABBC ABCDAB ABCDABCDABDE
以及其子串
ABCDABD
我们可知子串的最大长度表是
| A | B | C | D | A | B | D |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 2 | 0 |
下面我们来看一下比较时依次移动的位数
1.第一次失配向右移动了四位即跳过了BC和空格的匹配
2.第二次失配向右移动了四位
3.第三次失配移动了2位
4.第四次失配移动1位
5。第五次失配移动了四位
根据每次移动的位数和对应的最大长度表，我们可以按照下面的公式算出向后移动的位数
失配时，子串向右移动的位数为：已匹配字符数 - 失配字符的上一位字符所对应的最大长度值
既然是失配字符的前一位的话，那么我们是不是可以把最大长度表对应的值都同时向右挪一位，同时将初始值赋为-1，就可以得到下表。
| A | B | C | D | A | B | D |
|---|---|---|---|---|---|---|
| －1 | 0 | 0 | 0 | 0 | 2 | 2 |
这就是我们得到的next数组，进而我们可以得到以下推论
失配时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值