1 KMP算法概述
最近在写leetcode28的时候，想到了KMP算法。以前粗略地看过这个算法，也上网搜了很多的资料，但是却始终无法理解。最近又详细看了一遍，总算是找到点眉目了。因此做个记录，方便自己记忆。 问题描述：
pat 表示模式串，长度为 M，txt 表示文本串，长度为 N。请在txt 中查找子串 pat，如果存在，返回这个子串的起始索引，否则返回 -1。
2 暴力算法
想要理解KMP算法，那么暴力算法是必须理解的，建议对暴力算法不熟悉的，先自己手动写一遍暴力算法，再来深入理解KMP，我这边就不再赘述，直接贴出算法。
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.length() == 0)
return 0;
for(int i = 0; i < (int)(haystack.length() - needle.length() + 1); i++) {
for(int j = 0; j < needle.length(); j++) {
if(haystack[i + j] != needle[j])
break;
if(j == needle.length() - 1)
return i;
}
}
return -1;
}
};
暴力算法的时间复杂度是O(m * n)，因为对每一次匹配失败，我们都必须从头开始匹配。
3 KMP算法
3.1 KMP算法和暴力算法的不同之处
KMP算法本质上是对pat字符串的处理。 而暴力算法对pat字符串从不处理，因此每次出现不匹配的情况下，都需要从pat字符串的开头重新开始匹配，导致了重复的运算（前一次的匹配又计算了一遍）。 例如txt字符串为“aabaaabaaac，而pat字符串为”aabaaac”时，其中i指针指向txt字符串，j指针指向pat字符串。让我们从头开始匹配，直到i指针指向的字符不等于j指针指向的字符时，如图所示：
此时暴力算法会回退i指针和j指针，将i指针指向txt第二个字符，j指针指向pat的第一个字符，重新开始匹配。
而KMP算法从不回退i指针，而仅仅是对j指针进行回退，如下所示：
那么为什么能这么回退呢？
在第一个图中，此时i指向”b”，而j指向”c”，此时txt和pat的已匹配部分为aabaaa，由于已匹配部分后缀”aa”正好和前缀”aa”相同，因此可以将j回退到”b”，而不再是从头开始匹配。
这个特点就是我们KMP算法优化的核心部分。概括的讲就是：如果当前的字符不匹配，那么该跳到pat的哪个位置呢，从头开始，还是从某个特定的位置开始？这就是我们的next数组所解决的事情。它告诉了我们，如果当前字符不匹配，那么该跳转到哪个位置进行重新匹配。
根据这个特点，我们可以遍历pat，然后找出每个子串，其前缀后缀相同的最长长度，即next数组，之后使用这个next数组来遍历txt。
3.2 next数组
上一节中，我们初步认识了next数组，这一节我们详细理解next数组的原理，以及其如何求解。
next数组告诉我们，当前字符不匹配的时候，该跳转到哪个位置进行重新匹配。因此我们可以查看pat子串的前缀和后缀，并找出其最长的前后缀相同的长度，那么当不匹配的时候，我们可以从最长相同前后缀处开始匹配。
例如当我们匹配到子串aabaa的时候，此时这个子串的最长相同前后缀为aa，因此我们不必从头开始重新匹配，而是从字符b处开始匹配。因为我们知道aa是必定匹配的，就不必再比较了。
3.3 求next数组
如何在O(n)的时间内求解next数组是一个难点。
我们定义两个下标k和i，i下标从0开始，并且从不回退，表示next数组的下标；k从0开始，用来进行前缀匹配。
for (int i = 1, k = 0; i< n; ++i) {
while (k && pat[k] != pat[i]) k = next[k - 1];
if (pat[k] == pat[i]) k++;
next[i] = k;
}
3.4 整个匹配流程图
匹配代码如下： i指向被匹配字符串txt的下标，其永不后退，因此用for循环。 而j指向匹配字符串pat的下标，如果没有匹配上，那么j将会回退到next[j-1]的位置，因此采用while循环。
for (int i = 0; i < m; ++i) {
while (j && txt[i] != pat[j]) j = next[j - 1];
if (txt[i] == pat[j]) j++;
if (j == n) {
return i - n + 1;
}
}
return -1;
