个人理解仅供参考，若有不足请大家指出。
kmp 算法：无回溯的模式匹配算法，相比朴素的模式匹配算法减少了很多次没有意义的字符串比较从而使字符串的比较更加快速，高效。
KMP 模式匹配算法原理：
我们假设有主串 T = “ababefab”，子串 S = “ababa”。为了可以体现KMP算法的好处，我们先进行简单，粗暴的朴素模式匹配来与之相比：
- 朴素模式匹配:（串的序号从 1 进行开始标号）
| T串 | a | b | a | b | e | f | a | b |
|---|---|---|---|---|---|---|---|---|
| S串 | a | b | a | b | a |
第一步：设置两个指针 i 表示 T 串，j 表示 S 串，分别从序号 1 开始进行匹配：
- i = 1 ， j = 1 时匹配成功。
- i = 2 ， j = 2 时匹配成功。
- i = 3 ， j = 3 时匹配成功。
- i = 4 ， j = 4 时匹配成功。
- i = 5 ，j = 5 时，‘e’ != ‘a’ ，匹配失败。
第二步： 匹配失败，因此两个指针进行回溯，分别到回到 i = 2 ，j = 1, 继续进行匹配：
| T串 | a | b | a | b | e | f | a | b |
|---|---|---|---|---|---|---|---|---|
| S串 | a | b | a | b | a |
不难发现，当 i = 2 ，j = 1时匹配失败。
第三步：因此，继续进行回溯分别到回到 i = 3 ，j = 1, 继续进行匹配：
| T串 | a | b | a | b | e | f | a | b |
|---|---|---|---|---|---|---|---|---|
| S串 | a | b | a | b | a |
其实，我们根据 “子串的特点” 可以省去传统朴素算法中一些不必要的判断步骤，比如：
我们在第一步进行匹配时发现前面 4 个都匹配成功了，而在第 5 个的时候匹配失败了，所以要进行回溯，进行重新匹配，在回溯过程中我们发现子串中的 ‘a’ 与子串中第 2 位的 ‘d’ 是不同的，所以说，主串的第一位与子串的第一位是不可能相等的，因此，我们事先就知道匹配是不可能成功的，所以，第 2 步的比较就是多余的，我们可以去掉，当我们进行第三步匹配的时候，我们发现 S 串的前两位与 T 串相应的第 3 ，4位是匹配成功的，只有 T 串的第 5 位与 S 串的第三位是匹配失败的。有两个是成功的，那么，这个究竟为什么呐？先引入一个新的东西：
- 串的前缀与后缀：
前缀：指的是字符串的子串中从原串最前面开始的子串，如abcde的前缀有：a,ab,abc,abcd,abcd
后缀：指的是字符串的子串中在原串结尾处结尾的子串，如abcde的后缀有：f,ef,def,cdef,bcde
这里是理解KMP算法的关键所在。
对于，串 “abab” 来说，它的前缀有 ‘a’ , ‘ab’ , ‘aba’ ,后缀有 ‘b’ , ‘ab’ , ‘bab’ ,我们发现它们有相似的串 ‘ab’ ,对，这里的 ‘ab’, 与刚才第三步的已经匹配好前两位的 'ab’是有关系的；具体关系请看下图解释：
粉色与绿色是匹配成功的，即：粉色 = 绿色，假设我们经过对于子串特殊性的研究发现子串的只有红色与绿色是相同的，即：红色 = 绿色，那么，我们也可以说明红色与粉色是匹配的，即：红色 = 粉色。因此，我们可以利用找子串的规律来对传统朴素算法进行简化，省去那些我们已经知道是错误的比较次数，让其比较次数更少，更加高效，同时，这样我们也会发现这样的比较对于主串来说并没有进行回溯，只有子串在不断的调整位置。这就是我们找前后缀的最大相似度的原因所在，同时也解释了上面第三步比较所发生的情况。也是理解KMP算法高效的所在之处。
- NEXT数组推导：（寻找串的前后缀最大相似度）
对于 NEXT 数组推导，我们其实是把一个大串划分为许多的小串，对很多小串来求前后缀的最大相似度,最后储存在数组中，方便后续使用。
定义：(参考大话数据结构)
我们可以利用定义来分析一个推导过程。
T = “abcdex”
| j | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 串 T | a | b | c | d | e | x |
| next [j] | 0 | 1 | 1 | 1 | 1 | 1 |
过程如下：
1）当j=1时，next[1]=0；
2）当j=2时，j由1到j-1就只有字符“a”，属于其他情况next[2]=1；
3）当j=3时，j由1到j-1串是“ab”，显然“a”与“b”不相等，属其他情况，next[3]=1；
4）以后同理，所以最终此T串的next[j]为011111。
T = “abcabx”
| j | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 串 T | a | b | c | a | b | x |
| next [j] | 0 | 1 | 1 | 1 | 2 | 3 |
过程如下：
1）当j=1时，next[1]=0；
2）当j=2时，同上例说明，next[2]=1；
3）同理。
4）同理。
5）当j=5时，此时j由1到j-1的串是“abca”，前缀字符“a”与后缀字符“a”相等，因此可推算出k值为2（由‘p1…pk-1’=‘pj-k＋1…pj-1’，得到p1=p4）因此next[5]=2；
6）当j=6时，j由1到j-1的串是“abcab”，由于前缀字符“ab”与后缀“ab”相等，所以next[6]=3。
我们可以根据经验得到如果前后缀一个字符相等，k值是2，两个字符k值是3，n个相等k值就是n+1。
代码实现：
// next 数组推导：
void Get_Next(int next[], char* T) {
int i, j;
i = 1;
j = 0;
next[1] = 0;
while (T[0] > i) { // T[0]表示字符串的长度。
if (j == 0 || T[j] == T[i]) {
// T[j]表示前缀的单个字符。
++i; // T[i]表示后缀的单个字符。
++j;
next[i] = j;
}
else // 如果不相等，则指针退回。
j = next[j];
}
}对于 next 数组来说还有一点的缺陷，比如下面的例子：
S = “aaaabcde”，T = "aaaaax"时，我们发现利用 next 数组进行匹配还是不够高效，请看下图：(后面字符省略)
1.
| S串 | a | a | a | a | b | c | d | e |
|---|---|---|---|---|---|---|---|---|
| T串 | a | a | a | a | a | x |
2
| S串 | a | a | a | a | b | c | d | e |
|---|---|---|---|---|---|---|---|---|
| T串 | a | a | a | a | a | x |
3
| S串 | a | a | a | a | b | c | d | e |
|---|---|---|---|---|---|---|---|---|
| T串 | a | a | a | a | a | x |
4
| S串 | a | a | a | a | b | c | d | e |
|---|---|---|---|---|---|---|---|---|
| T串 | a | a | a | a | a |
5
| S串 | a | a | a | a | b | c | d | e |
|---|---|---|---|---|---|---|---|---|
| T串 | a | a | a | a |
6
| S串 | a | a | a | a | b | c | d | e |
|---|---|---|---|---|---|---|---|---|
| T串 | a | a | a |
其next数组值分别为012345，在开始时，当i=5、j=5时，我们发现“b”与“a”不相等，如上图的 1，因此需要回溯，即：j=next[5]=4，如图中的 2，此时“b”与第4位置的“a”依然不等，同理，j=next[4]=3，如图中的 3，后依次是 4 5，直到j=next[1]=0时，根据算法，此时i++、j++，得到i=6、j=1，如图中的 6。
我们发现，当中的 2 3 4 5 步骤，其实是多余的判断。由于 T 串的第二、三、四、五位置的字符都与首位的“a”相等，那么可以用首位next[1]的值去取代与它相等的字符后续next[j]的值，这是个很好的办法。因此我们对求next函数进行了改良。
4.nextval数组推导：
例如：
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 串T | a | a | a | a | a | a | a | a | b |
| next[j] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| nextval[j] | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 8 |
推导过程：
1）当j=1时，nextval[1]=0；
2）当j=2时，next值为1，第二个字符与第一个字符相等，所以nextval[2]=nextval[1]=0；
3）同样的道理，其后都为0……；
4）当j=9时，next值为8，第九个字符“b”与第八个字符“a”不相等，所以nextval[9]=8。
代码改进：
// nextval 数组推导：
void nextval(int nextval[], char* T) {
int i, j;
i = 1;
j = 0;
nextval[1] = 0;
while (i < T[0]) {
if (j == 0 || T[i] == T[j]) {
++j;
++i;
if (T[i] != T[j]) {
nextval[i] = j;
}
else
nextval[i] = nextval[j];
}
else
j = nextval[j];
}
}
到现在KMP的重难点知识已经基本说完了。剩下的就是匹配过程了，没有什么可仔细说的了。
;