问题描述
KMP算法是用与字符串匹配的算法，给定文本串，在文本串中寻找模式串，如果找到匹配的模式串便返回文本串首次出现模式串的首字符的地址
算法分析
1th
最简单最暴力的算法便是逐一匹配全部字串，该算法的时间复杂度为O(m*n)，其中m为文本字符数，n为字串数
思路如图示：
遇到匹配失败后
逐一遍历文本串，来匹配模式串，直至匹配成功，或者匹配到最后无可匹配
Code
char text[m];
char pattern[n];
for ( i = 0; i < m; i++) {
for ( j = 0; j < n && (i + j) < m; j++) {
if (pattern[j] != test[j + n]) {
break;
}
}
if (j == n) {
return true;
}
}
return false;
2th
为什么1th版本会很慢？是因为做了很多的无效匹配，以上面的例子为例，当遍历到text[3]时匹配失败，指针退回了text[1]。每一次失败的匹配只会重新在下一位继续匹配。从上述例子可以看出从text[1]继续下去匹配只会还是失败。这便是为什么慢的原因
这里事先说明，这里所说的指针不是C语言中的指针，是更范的概念，表示所指元素的地址（不一定是计算机内部的地址，可以是数组下标
i为模式串的指针
j为文本串的指针
KMP的算法便做了一个优化，i不会回退，每一次遍历只会向前，不会像前面那样，从text[3]的匹配失败回退到text[1]。
如图所示：
匹配失败
回退之后，匹配成功：
再次失败：
回退之后，再次失败，但是无法回退了：
直到最后匹配成功或者失败
总结一下图中所示：遍历文本串的指针是不会后退的，只会一直向前。会后退的是模式串的指针
每次pattern[i]匹配失败，对应的文本串的 j 指针便会回退到一个合适的位置（什么是合适的位置？后面将会详细的讲解）然后从这个位置再继续匹配，如果仍旧匹配失败，继续回退，直到匹配成功或者不能再回退为止。
无论最后合适的位置是否匹配，i 都会向前
Code
bool KMP(char text[], char pattern[]) {
int n = strlen(text);
int m = strlen(pattern);
getNext(pattern, m);
int j = -1;
for (int i = 0; i < n; i++) {
while (j != -1 && text[i] != pattern[j + 1]){//寻找合适位置，直到匹配成功或者无可回退
j = next[j];
}
if (text[i] == pattern[j + 1]) {//在pattern[i]匹配成功，移动 j
j++;
}
if (j == m - 1) {//表示匹配成功
return true;
}
}
return false;
}
注意上面text[j + 1]才是和pattern[i]相匹配的, j 是相匹配下标的前一位
j = next[j];便代表 j 的回退，而next数组正是管理着文本串每个字符的回退下标，也就是所谓的合适位置
下面开始讲解Next数组
Next数组
假设一个字符串s和一个next数组（长度相等且为l）
next[k]（k <= l )里的值等于s的子串n[0....k]的最长相等前后缀的前缀最后一个元素的下标，如果找不到相等的前后缀，便取-1；
如图所示：
字符字串n = abcab的最长前后缀为ab，所以next[4] = 1
而整个next数组里存放的值便是字符串s(长度为n）的字符字串[0....k](k <= n)的最长相等前后缀的前缀最后一个元素的下标，如果没有相等的前后缀，便设为-1
也许有人还不明白这最长前后缀的作用，那么便解释一下：
当pattern[i] != text[j+1]时，我们便找到字符串k[0...j]的最长前缀的下标，从该最长前缀继续往下匹配(通过更新j来继续匹配 j = next[j])*，如果还不匹配再找该前缀的最长前缀的下标，直到找到可以匹配或者j = -1
那么如何求出next数组的值呢？
假设我们有一个字符串s[0...k]，并且已知next[0....k-1]的值，现在我们要求next[k]
那么我们怎么求呢？因为我们有了字符串n[0....k-1]相对应的next[]值，所以我们就可以通过比较s[k]是否等于n[0...k-1]的最长子缀的后一位字符来确定next[k]!，如果相同意味着next[k] = next[k - 1] + 1，如果不相同，便找m[0...next[k - 1]]的后一位元素相比较，因为问题条件中next[0...k-1]我们都是知道的！，一直往下递归，直到找到有个前缀的后一个元素与之相同（这个就是s[0...k]的最大前缀，仔细想想）或者没有前缀与之相等（设为-1）
Notice！next[n]里的的值代表字符串m[0...n]的最长前缀的最后一位元素的下标，不要弄晕了
好了，求法我们已经完成了一大半。如果我们有字符串s[0...k+1], 并且已知next[0...k]的值，然后求next[k+1]，这个过程是否似曾相识呢？
我们只需设定next[0] = -1；便可以一直往下推出剩下的next值（假定只有一个字符的串没有相等的前后缀）
Code
void getNext(char s[], int length) {
int j = -1;
next[0] = j;
for (int i = 1; i < length; i++) {
while (j != -1 && s[i] != s[j + 1]) {//不停回退，直到找到或者等于j = -1
j = next[j];
}
if (s[i] == s[j + 1])//找到
j++;
next[i] = j;
}
}
next数组和kmp结合起来一看，便是当k+1匹配失败之后，k便回退到next[k]继续匹配，直到可以匹配或者k = -1重新匹配
next找到最大前缀，kmp使用最大前缀来实现 i 一直向前遍历
nextval数组
nextval是next的高配版，next数组存在多次更新情况，也就是可能回退多次才能找到最终合适的位置，而nextval一步到位直接找到最合适的位置
s[0...4] = ababa 最大前缀为aba aba的最大前缀为a
如果s的[5] = b,如果匹配失败，便会继续匹配s[3], s[1]而它们也正好都是b，因此多了几次无谓的比较
所以一旦s[5]比较失败，便直接回退到-1，也就是其该字串的前缀之后的第一个元素不等于该字串的之后的第一个元素的最大前缀
只需添加s[j + 1] == s[i +1]这一判断条件
如果成立，nextval[j] = nextval[i];
否则，nextval[j] = i;
Summary
总的来说，KMP是利用了最大前缀来节省了时间，保证pattern一直向前遍历，而且text串也最大程度地节省了匹配位数
KMP算法是AC自动机的特殊情况，有兴趣可以阅读之后AC自动机讲解
