KMP算法手推详解
要搞懂kmp算法，首先要了解next数组
那么，next数组到底是求什么的呢？
举个例子，有一个字符串abcabdabc,
要求它的最长的相同前缀后缀。
所谓前缀，就是包含了首字母的字符串字串；
所谓后缀，就是包含了末尾字母的字符串字串。
所以啊，这个abcabdabc的最长的相同前缀后缀呢，显然是abc这个字串，长度为3.
而这个字符串的next数组是什么意思呢？：
next[0],就是求a的最长相同前缀后缀，并把长度存储进next数组；
next[1],就是求ab的最长相同前缀后缀，并把长度存储进next数组；
next[2],就是求abc的最长相同前缀后缀，并把长度存储进next数组；
…
next[8],就是求abcabdabc的最长相同前缀后缀，并把长度存储进next数组。
现在，为了简化代码，我们对这个next数组做一个约定：
1.当字符串没有相同前缀后缀时，next存储的长度为-1，显然，next [0]=-1。
2.当字符串有相同前缀后缀时，next存储的长度为其长度-1。
看到这，你应该试试自己写一个字符串，并试着推出next数组的代码了。
static void Next(String str) {
int length = str.length();
next = new int[length];
int k = -1;
next[0] = -1; //第一个数必定为-1
for (int i = 1; i -1 就是先找到与第一个数相同的数
while (k > -1 && str.charAt(k + 1) != str.charAt(i))//如果下一个不同，那么k就变成next[k]，注意next[k]是小于k的，无论k取任何值。
{
k = next[k];//往前回溯 例如（agctagc）（agctagc）t 比较到t时 k=next[6]=2 t=3 即前面有子对称 且与t匹配
//如果是（abcdefg)(abcdefg)t k=next[6]=-1，即前面没有子对称
//如果是（agc$$$agc)(agc$$$agc)t k=next[8]=2=next[2]=-1; 前面虽然有子对称 但是子对称后的数 与t不匹配
}
if (str.charAt(k + 1) == str.charAt(i))//如果相同，k++
{
k = k + 1;
}
next[i] = k;//这个是把算的k的值（就是相同的最大前缀和最大后缀长）赋给next[q]
}
}
仔细思考下这段代码和注释，如果还是看不懂，没关系，坚持一下，我们接着看下面的：
举个例子，我们求（agctagc)(agctagc)t,这一个字符串的next数组。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| -1 | -1 | -1 | -1 | 0 | 1 | 2 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 3 |
上面的是next数组的下标，下面是next数组里面存储的值。
根据代码，我们在脑海里跑一遍，发现，其实到13的时候，都很好理解。
唯独计算最后一个t的的时候，有一句k=next[k]，不太好理解。
这句话到底是啥意思呢。我们根据表格，看到t的值是3,
因为这个字符串t前面的地方存在着内部子对称，思考一下，agctagc与agctagc是对称的,而k=next[k]>0的话，说明agctagc之间也存在着子对称,说明啊，这前面括号里面的字符串的前缀与后面括号的字符串的后缀有相同的可能，这样，我们就可以直接比较他们的后一位是否相同了。
如果不同，在接着k=next[k],查找字符串前面是否还存在子对称，知道不存在为止。
这就是k=next[k]的含义。
static int kmp(String haystack, String needle) {
int length1 = haystack.length();
int length2 = needle.length();
if(needle.length()==0||haystack.length()==0)
{
return 0;
}
Next(needle); //计算needle的next数组
int k = -1;
for (int i = 0; i -1 && needle.charAt(k + 1) != haystack.charAt(i))//k>-1 即先找到haystack中与needle首字母相同的元素
k = next[k];//往前回溯
//such as 在(agctagc）（agctagc）t 中查找agctagct k=next[6]=2=next[2]=-1
//之所以把k=next[k]向前回溯 是因为 如果next[k]>0 则模式串存在子对称 所以模式串的前缀与刚刚匹配的文本串后缀相同
// 所以可以直接把k滑到next[k],其实相当于把i滑到了next[i]
if (needle.charAt(k + 1) == haystack.charAt(i)) //元素相同则比较下一位是否也相同
k = k + 1;
if (k == length2 - 1)//说明k移动到ptr的最末端
{
//cout << "在位置" << i-plen+1<< endl;
//k = -1;//重新初始化，寻找下一个
//i = i - plen + 1;//i定位到该位置，外层for循环i++可以继续找下一个（这里默认存在两个匹配字符串可以部分重叠），感谢评论中同学指出错误。
return i - length2 + 1;//返回相应的位置
}
}
return -1;
}
下面我们来解释kmp算法·，其实这和next数组求法很像。
同样地，举个例子。
文本串abcabcabc 模式串abcabd
| a | b | c | a | b | c | a | b | d |
|---|---|---|---|---|---|---|---|---|
| a | b | c | a | b | d |
显然，这时候c与a不匹配，那么，如果我们还没有了解过kmp算法，我们的第一直觉是，滑动上面的文本串指针，让指针指到第二个a,也就是这样：
| a | b | c | a | b | c | a | b | d |
|---|---|---|---|---|---|---|---|---|
| a | b | c | a | b | d |
但是，为什么要滑到第二个a呢，我们可以发现，文本串的后缀与模式串的前缀有相同的，我们利用这个信息，可以把文本串滑过去，就不用一步一步滑了。
但是！！！ 这只是我们观察的结果，实际上要在代码中利用这个信息来滑动文本串指针是非常困难的。
于是，KMP三位大牛们想到了另外一个法子：滑动模式串。
怎么来滑动模式串呢？
我们接着来看刚才这个表格
| a | b | c | a | b | c | a | b | d |
|---|---|---|---|---|---|---|---|---|
| a | b | c | a | b | d |
这时候c与d不匹配，上面的文本串指针指到c，它不能被滑动。
那我们的想法是什么呢？我们把下面的模式串指针滑倒c上，比较它与上面的c是否相等，如果相等，则接着同时比较下一位，这时我们就能找到结果了。
那如果下面这个c与上面的c不相等呢，那我们就接着找，还有没有这样的文本串后缀与模式串前缀相同的地方。
用代码来描述就是：
for (int i = 0; i -1 && needle.charAt(k + 1) != haystack.charAt(i))//k>-1 即先找到haystack中与needle首字母相同的元素
k = next[k];//往前回溯
//such as 在(agctagc）（agctagc）t 中查找agctagct k=next[6]=2=next[2]=-1
//之所以把k=next[k]向前回溯 是因为 如果next[k]>0 则模式串存在子对称 所以模式串的前缀与刚刚匹配的文本串后缀相同
// 所以可以直接把k滑到next[k],其实相当于把i滑到了next[i]
if (needle.charAt(k + 1) == haystack.charAt(i)) //元素相同则比较下一位是否也相同
k = k + 1;
if (k == length2 - 1)//说明k移动到ptr的最末端
{
return i - length2 + 1;//返回相应的位置
}
k=next[k]!!! 这个式子，就是下面的模式串指针在不相等时该滑动的地方。
当k=next[k]>0的时候，即模式串存在子对称，我们直接把指针滑到这个对称的地方，而i是一直在自增的。
用这种方式，我们就用滑动模式串来间接地实现了滑动文本串。这就是kmp
算法！
我相信，只要你认真看了和跟着例子思考了这篇博文，即使你是刚接触代码的初学者，也能透彻理解KMP算法，因为这个算法本身没有太多的偏僻的知识点，仅仅是一名初高中生，我觉得也能理解它。
作者：儿时凿壁偷了谁家的光
