KMP是一种不太常用的字符串匹配算法，但是在某些情况下，依然可以发挥作用，而它的next思想，更是可以应用在别的地方。
这是我第三次总结KMP算法，第一次是在ACM集训后填坑期间，第二次是在学《数据结构》补充笔记的时候，因为三次的目的不同，这次的侧重点应该是KMP算法本身，希望写出来的总结能对周老师和大家有些许帮助。
朴素算法
在说KMP算法前，必然要说朴素算法，也就是我们常用的字符串匹配算法。
假设我们有一个S串和一个T串，我们需要判断S串中是否包含一个T串，或者找到T串首次出现的位置等操作。一般情况下，我们会进行如下的操作：
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
char[] S = scanner.next().toCharArray();
char[] T = scanner.next().toCharArray();
boolean isFind = false;
for(int i = 0;i < S.length;i++){
isFind = true;
for(int j = 0, ti = i;j < T.length;j++, ti++){
if(ti == S.length){
isFind = false;
break;
}
if(S[ti] != T[j]){
isFind = false;
break;
}
}
if(isFind){
break;
}
}
System.out.println(isFind ? "YES" : "NO");
}
}
当然，如果硬要说这种情况不好还想进行优化的话，可以进行优化的地方还是很多的，KMP便是针对指针回溯进行优化的算法。
什么是指针回溯
如上文的两个for循环，其中的 i，ti 和 j 分别对 S 和 T 串进行位置标记，然后进行比较等操作，我们可以把 i，ti 和 j 看做三个标记指针，而在每一轮的比较中（也就是内循环break前算作一轮比较），ti 和 j 进行不断向后移动进行比较，然而如果比较失败（发现了不同），那么，ti 就会回溯到 i + 1 的位置（当本次内循环结束，再次执行内循环时 i 已经进行了自增操作。），而 j 指针会回溯到 0 （也就是T串的开始位置），然后进行再次比较，以此重复直到找到匹配位置或者外循环结束。
如果看算法流程的话，可以更明显的看出指针回溯。
算法流程
- i 指向S串开始
- j 指向T串开始，ti 指向和 i 相同的位置
- 对 j 指向的字符和 ti 指向的字符判断 相同？执行4：执行6
- j 指针后移，ti指针后移
- j 或 ti 指向 S 或 T 串的结尾 ？ 执行6：执行3
- i 自增
- i 指向S串的结束？执行8：执行2
- 打印结果
改良方向假设
很明显，如果我们可以做到两个指针减少回溯，或者保证一个不回溯，是不是就可以减少无用的匹配。
为了方便说明，我们可以举一个极端的栗子：
对于S串和T串是上图的样子，如果使用朴素算法，在匹配失败的时候，i指针（现在指向S串的第10个元素'a'）应该会回溯到S串的第4个元素 'b' 上，而 j 指针，也会从T串的第8个元素'c'，回溯到T串的第1个元素'a'上，然后进行重新循环比较。
而我们很明显可以看出来，这并不是最佳方案，最佳方案应该是i指针稳住不动，继续指向第10个元素，而j指针回溯到第1个元素上。因为很明显，i在前10个元素处不会有全匹配。
当然，这是我们已经可以一眼看到全局而能做出的最佳方案，而程序是不可能眼观全局的，但不意味着程序做不出这样的判断。
我们假设程序虽然不知道S串后面是什么样子，但已经知道了 T 串的构造和 T 串与 S 串已经匹配的部分，那么就应该可以做到清楚的知道指向 T 串的 j 指针应该怎么移动而可以避免回溯指向 S 串的 i 指针。
那么，如果上面说的不是神话，则明白 T 串的构造便是实现上述想法的关键。
因此，KMP算法诞生了。
KMP算法
终于讲到正题了，正如上文所说，与朴素算法相比，KMP算法多了对 T 串的构造进行分析，从而诞生了next数组。而next数组，便是整个KMP算法的核心，不仅仅是字符串匹配，在前缀，后缀，循环节判断等方面，next也能发挥重大作用。
next数组的意义
要想清楚什么是next数组，next数组的意义，切入点便是next数组在匹配中起到的作用。
还是这张图，朴素算法的缺点是什么呢，就是说：匹配过的就是做的无用功，不管你匹配多么长,都是按照没匹配过，无情的从开头再来一遍,这就导致了时间的浪费。
如果我们匹配过以前的，不再放弃了，而是利用匹配过的信息推导出有用的信息。目的就是：匹配过的 S 串中还有多少直接等于 T 串的 ，假设知道了这个信息，是不是将会节省不少事件。
因此，next中就是保存的匹配过的 S 串中还有多少直接等于 T 串的。
假设我们开始匹配的时候i指针指向了S[e]，j指针指向T[0]，进行了k次比较之后发现不同，也就是比对失败了，我们是不是可以得出结论：S[e,e+k] = T[0,k]
而如果我们的next数组已经记录了匹配过的S串中还有多少直接等于T串的，假设这个值为t，那么是不是也就意味着：S[e',e'+k] = T[0,t]。
如下图所示：
利用意义上的 next 数组得出 kmp 算法
定义： 此字符串的开头到某一位置称为这个字符串的前缀,，从某一个位置到这个字符串的最后位置称为这个字符串的后缀。
于是，我们需要截取所有的前缀来匹配后缀，因为 T 串在匹配时可能会用到各式各样的前缀，我们 next[]数组就是为了，一个前缀一个最大前后缀匹配值。
因此，求next数组的代码就出来了：
private int[] getNext(){
char[] chars = this.str.toCharArray();
int len = chars.length;
int[] next = new int[len + 1];
int k = -1, i = 0;
next[0] = -1;
while(i < len){
if(k == -1 || chars[k] == chars[i]){
i++;
k++;
next[i] = k;
}else{
k = next[k];
}
}
return next;
}
（这是从今天的KMP题目SDUTOJ 2784中直接取出来的一个方法）
有了next数组后，当失配时，固定 i 指针不动，直接利用 T 串的 next 值滑，将我们知道的信息(我们知道到哪里的前缀和后缀相等)再次验证一遍来浪费时间。
那么我们的匹配算法就可以写作下面这个样子：
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
char[] S = scanner.next().toCharArray();
char[] T = scanner.next().toCharArray();
boolean isFind = false;
int j = 0;
for(int i = 0;i < S.length;i++){
if(j == T.length){
isFind = true;
break;
}
if(S[i] == T[j]){
i++;
j++;
}else{
j = next[j];
}
}
System.out.println(isFind ? "YES" : "NO");
}
}
由两个for循环嵌套变成一个是不是很爽的样子！！
当然，这只是next的常规用法（字符串匹配），而next的灵活用法还有很多（比如刚才说的前缀后缀什么的，还包括SDUTOJ 2784）。
结束语
这篇文章只是KMP总结和next数组的介绍，作为SDUTOJ 2784解题报告的前置技能 (:з」∠)。
文中插图/定义引用了王政（@9cai）同学在队期间写的《Kmp 算法引论》（好流弊的名字^_^），因为Linux下做图片麻烦，也懒得去做图片了。
文章写成仓促，重点放在KMP与朴素算法比较和next的引入上，可能文章中存在些许问题，欢迎指正。
最后，引用我第二次对KMP总结文的内容作为结束语：
- 传统算法（朴素算法）最坏情况是O(nm)，但一般是在O(n+m)，也不是太坏，所以一般没有特殊要求的程序还在用这种算法；
- KMP算法在有大量重复的情况下优化明显，对主串较大时比较有效；
- next函数还是有缺陷的，比如模式串’aaaab’与主串’aabaaaab’匹配时，用时几乎和朴素算法一样；
- 以发展的眼光看问题，其实作为常用算法之一，匹配算法也有发展，KMP已经不是主流。
