KMP 算法（Knuth-Morris-Pratt 算法）是一个著名的字符串匹配算法，效率很高，但是确实有点复杂。
在实际生活中，字符串查找是非常常见的，在一段信息中匹配到你需要寻找的信息（就是在一段字符串找到需要匹配的字符串），那么怎样去寻找呢？
我们运用暴力匹配的时候，每次都匹配了很多此无意义的字符，什么意思呢？ 请看：
我们从这里开始匹配
因为主串【i】和匹配串【j】一直不相等，所以主串右移
现在主串【i】和匹配串【j】相等开始匹配，i和j一起右移
现在它们又不相等了，所以
按照暴力匹配的算法思想： 此时应该将i回溯，将i回到原来开始的位置的下一个位置，j归零。代码中的表现就是 i-(j-1)，j=0，但这样效率实在太差，我们已经知道关于字符串一部分信息了，我们怎样运用这部分加速匹配信息呢？这里就要用到
KMP算法了
主要是消除了主串指针的回溯，之后效率就提高
KMP 算法主要是通过消除主串指针的回溯来提高匹配的效率的，那么，它是则呢样来消除回溯的呢？就是因为它提取并运用了加速匹配的信息！
这种信息就是对于每模式串 t 的每个元素 t j，都存在一个实数 k ，使得模式串 t 开头的 k 个字符（t 0 t 1…t k-1）依次与 t j 前面的 k（t j-k t j-k+1…t j-1，这里第一个字符 t j-k 最多从 t 1 开始，所以 k < j）个字符相同。如果这样的 k 有多个，则取最大的一个。模式串 t 中每个位置 j 的字符都有这种信息，采用 next 数组表示，即 next[ j ]=MAX{ k }。
加速信息就是next数组
遇到像上图的情况怎样优化？
如果我们自己用人脑去思考，用眼睛去看：
到这里我们就可以得到了基本思路了，又该怎样去实现它呢？
实在不好描述，懂得都懂，因为我们现实生活比就是这样比，如果硬要描述，请看下面：
到了这里我们可以大概看出一点东西，当匹配失败时，j要移动的下一个位置k。存在着这样的性质：最前面的k个字符和j之前的最后k个字符是一样的。
如果用数学公式来表示是这样的
P[0 ~ k-1] == P[j-k ~ j-1]
当T[i] != P[j]时
有T[i-j ~ i-1] == P[0 ~ j-1]
由P[0 ~ k-1] == P[j-k ~ j-1]
必然：T[i-k ~ i-1] == P[0 ~ k-1]
0 A
0 AB
0 ABC
1 ABCA（这里就是最大前缀A和最大后缀B）
2 ABCAB（类似：AB）
0 ABCABA（AB）
最大前缀和最大后缀的解释：比如ABCABA的前缀有{A,AB,ABC,ABCA,ABCAB}
最大后缀：{A，BA,ABA,CABA,BCABA}
这里解释下，因为自己最开始也理解不对
在匹配串的每个位置都有可能发生不匹配，所以要计算没一个k（其实最后一个可以不算，但也可以，这里我们算，其实感觉不算更好）我们首先要知道next【j】=k,表示当它们不匹配时，j指针的下一个位置 （非常重要），还有就是，因为字符串是从下标0开始的，所以j位置之前的最大重复子串（最大相同前后缀），注意是j位置之前
public int[] getNext(char[]parm){
int next[]=new int[parm.length];
next[0]=0;
int i=0;
int k=1;
while(k<parm.length){
if(parm[i]==parm[k]){
next[k++]=++i;
}else{ if(i>0){
i=next[i-1];
}else {
next[k++]=i;
}
}
return next;}
}
记住最重要的东西：next数组中保存的是当它们不匹配时，j指针要移动的位置
当它们匹配的时候怎么求next数组呢？这里我们可以发现用前缀表看出来
比如：ABAB
next【3】=1
next【4】=2
所以当它们匹配的时候就有：next【j+1】=next【j】+1
证明：
因为在P[j]之前已经有P[0 ~ k-1] == p[j-k ~ j-1]。（next[j] == k）
这时候现有P[k] == P[j]，我们是不是可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。
即：P[0 ~ k] == P[j-k ~ j]，即next[j+1] == k + 1 == next[j] + 1。
p为匹配串
这里也是next数组最重要的部分
k=next【k-1】(我这里用的是k=next【k-1】，很多博客时用到的是k=next【k】，
因为我们求得是k位置之前的最大重复子串（最大相同前后缀，所以保存的位置可能不同，这和后面的一个解释也相互验证）
其实就是当k和j不相同的时候，就把k之前的字符串看做要匹配的串，后面的字符串看做主串，所以当它们不匹配的时候，就要和kmp算法的处理阶段一样，把它们移动到可能的地方.
其实可以用数学归纳法证明出来，
但解释语言比较长，现在天色已晚，后面有时间再补
class Solution {
public int strStr(String haystack, String needle) {
if("".equals(needle)){
return 0;
}
char[] noodleArr=haystack.toCharArray();
char[] parmsArr=needle.toCharArray();
int i=0;
int j=0;
int[] next=getNext(parmsArr);
while(i<noodleArr.length && j<parmsArr.length){
if(noodleArr[i]==parmsArr[j]){
i++;
j++;
}else{
if(j>0){
j=next[j-1];
}else{
i++;
}
}
}
if(j==needle.length()){
return i-j;
}else{
return -1;
}
}
public int[] getNext(char []parm){
int[] next=new int[parm.length];
next[0]=0;
int k=1;
int j=0;
while(k<parm.length){
if(parm[k]==parm[j]){
next[k++]=++j;
}else{
if(j>0){
j=next[j-1];
}else{
next[k++]=j;
}
}
}
return next;
}
}
因为一些小细节的实现可能和其他博客不一样，所以特此进行说明
造成的结果是：
我的next数组每个位置保存的是当前位置的最大重复子串。但每次不匹配的时候，
要移动到的位置就是不匹配位置k之前的最大子串长度 （注意是k之前）
所以我的是k=next[k-1]
2.下面这段代码的一些小细节：
最开始我是这样写的（注意划红线的地方）
if（j>0）{
j=next[j-1];
}else if(j==0){
i++;
}
最开始真的没仔细思考，没想到当j=next[j-1]=0，之后造成了又进去了一次，其实这次完全是没必要的，这里就是当j=0时，i++，就是当它们一开始（i=0，j=0）就不匹配的时候，
这就是上面代码说明中的第2种情况
这是没考虑当要匹配的字符串长度为0的情况
自己也一脸蒙蔽，当时也没处理（debug）因为其他事耽搁了
建设字符主串的长度为m，模式串为n
有了代码过程就很容易得到时间复杂度 我们得到结果的条件是，字符主串或者模式串读完（注意是读完，不是读到）结尾，所以很容易就知道是O(N+M)
为什么我用kmp算法表现还差些？是它用测试用例很极端吗？
暴力算法：
KMP算法：
这个题目还有个捷径：直接用Java的内置函数（indexof（））
1. 发现自己对Java基础知识（比如集合）有点遗忘啊（过度依赖idea的提示功能了）
2. 自己应该以计算机的方式去思考
原文：https://www.cnblogs.com/zcqzwy/p/14004970.html