KMP算法是解决字符串匹配的常用算法之一，也就是在主串（比如aabbccdd）中的子串（bc）定位问题。子串称为P，如果它在一个主串称为T中出现，就返回它的具体位置，我们先来看看普通的字符串匹配是怎么做的
最基础的匹配
思路：从左到右一个个匹配，如果这个过程中有某个字符不匹配，将子串向右移动一位，继续从左到右一一匹配。
当匹配到如图第四个字符位置后，匹配失败，子串后移，继续匹配
第一位匹配失败，继续后移...
直到匹配成功
[图片上传失败...(image-bdd392-1548667452278)]
代码如下：
public class Normal {
public static void main(String[] args) {
int index = bf("ABCABCEFG", "ABCE");
System.out.println(index);
}
public static int bf(String ts, String ps) {
char[] t = ts.toCharArray();
char[] p = ps.toCharArray();
int i = 0; // 主串的位置
int j = 0; // 子串的位置
while (i < t.length && j < p.length) {
if (t[i] == p[j]) { // 当两个字符相同，就比较下一个
i++;
j++;
} else {
i = i - j + 1; // 一旦不匹配，i后退
j = 0; // j归0
}
}
if (j == p.length) {
return i - j;
} else {
return -1;
}
}
}
这种方式是效率最低，匹配次数最多的情况，接下来看KMP的解决思路
KMP中的PMT
KMP在遇到下图位置时，不会很无脑的把子串的j移动到第0位，主串的i移动到第1位，然后进行T[i]==P[j]的比较
[图片上传失败...(image-1dbb87-1548667452278)]
因为从图上可以看得出后移一位后子串前三位（ABC）和主串的T[1-4]（BCA）肯定是不匹配的，无需白白浪费这几次比较，最好应该是直接让i不变，j==0，如下图
从这里开始匹配，省去了前面的几次无用匹配。
KMP思想：利用前面匹配的信息，保持i指针不变，通过修改j指针，让子串尽量地移动到有效的位置。
整个KMP的重点就在于当某一个字符与主串不匹配时，我们应该知道j指针要移动到哪？
先用肉眼来看一下规律：
如图：C和D不匹配了，我们要把j移动到哪？显然是第1位。为什么？因为前面有一个A相同可以用：
再看一种：
可以把j指针移动到第2位，因为前面有两个字母是一样的：
我们可以看出来，匹配失败的时候，j变为k,j前面的的n个字符等于子串开头到k位置的n个字符的值
即：P[0 ~ k-1] == P[j-k ~ j-1]
这时我们发现规律了，其实就是要求当前j之前的字符串也就是ABCAB它的首尾对称的长度最大长度也就是PMT值。
PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。
例如，对于”aba”，它的前缀集合为{”a”, ”ab”}，后缀集合为{”ba”, ”a”}。
两个集合的交集为{”a”}，
那么长度最长的元素就是字符串”a”了，长度为1，所以对于”aba”而言，它在PMT表中对应的值就是1。
再比如，对于字符串”ababa”，它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”}，
它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}，
两个集合的交集为{”a”, ”aba”}，其中最长的元素为”aba”，长度为3。
所以上面最后一个图的情况下，j位置之前的字符串的PMT值为2，所以j的值变成2。
KMP之next数组
那么好了接下来核心就是求得P串每个下标元素对应的k值即可，因为在P的每一个位置都可能发生不匹配，我们要计算每一个位置j对应的k，所以用一个数组next来保存，next[j] = k，表示当T[i] != P[j]时，j应该变为k。
求next数组代码如下
public class Next {
public static int[] getNext(String ps) {
char[] p = ps.toCharArray();
int[] next = new int[p.length];
next[0] = -1;
int j = 0;
int k = -1;
while (j < p.length - 1) {
if (k == -1 || p[j] == p[k]) {
next[++j] = ++k;
} else {
k = next[k];
}
}
return next;
}
}
通过上面代码可以直接算出j为0和1时的k，当j为0时，已经无法后退了所以设置为-1初始化值，当j为1时，它的前面只有下标0了，所以next[0]=-1,next[1]=0.
接下来就是两种主要情况了
if (k == -1 || p[j] == p[k]) { 第一种p[j] == p[k]
next[++j] = ++k;
} else { 第二种p[j] != p[k]
k = next[k];
}
第一种p[j] == p[k]
p[j] == p[k]时，有next[++j] = ++k;
因为当在p[j-1]处匹配失败后，j-1变为k-1，从k-1处重新开始匹配，原因就是他们共同有一个前缀A，所以当p[j] == p[k]后，他们就拥有了前缀AB所以k++；
第二种p[j] != p[k]
此时代码是：k = next[k];原因看下图
像上边的例子，我们已经不可能找到[ A，B，A，B ]这个最长的后缀串了，但我们还是可能找到[ A，B ]、[ B ]这样的前缀串的。所以这个过程就像在定位[ A，B，A，C ]这个串，当C和主串不一样了（也就是k位置不一样了），那当然是把指针移动到next[k]。
有了next数组之后就一切好办了，我们可以动手写KMP算法了：
public class Kmp {
public static int KMP(String ts, String ps) {
char[] t = ts.toCharArray();
char[] p = ps.toCharArray();
int i = 0; // 主串的位置
int j = 0; // 模式串的位置
int[] next = getNext(ps);
while (i < t.length && j < p.length) {
if (j == -1 || t[i] == p[j]) { // 当j为-1时，要移动的是i，当然j也要归0
i++;
j++;
} else {
// i不需要回溯了
// i = i - j + 1;
j = next[j]; // j回到指定位置
}
}
if (j == p.length) {
return i - j;
} else {
return -1;
}
}
}
KMP改进
KMP算法是存在缺陷的，来看一个例子：比如主串是aaaabcde，子串是aaaaax，next值为012345，当i=5时，如下图：
我们发现，当中的②③④⑤步骤，其实是多余的判断。由于子串的第二、三、四、五位置的字符都与首位的“a”相等，那么可以用首位next[1]的值去取代与它相等的字符后续next[j]的值，这是个很好的办法。因此我们对求next函数进行了改良。
public class Next2 {
public static int[] getNext(String ps) {
char[] p = ps.toCharArray();
int[] next = new int[p.length];
next[0] = -1;
int j = 0;
int k = -1;
while (j < p.length - 1) {
if (k == -1 || p[j] == p[k]) {
if (p[++j] == p[++k]) { // 当两个字符相等时要跳过
next[j] = next[k];
} else {
next[j] = k;
}
} else {
k = next[k];
}
}
return next;
}
}
