字符串匹配的KMP算法
算法概述
算法主要用于子串的定位，即串的模式匹配。
算法的心路历程
字符串中前缀和后缀的概念：
- “A”的前缀和后缀都为空集，相等的前缀后缀长度为：0
- “AB”的前缀为[A]，后缀为[B]，相等的前缀后缀长度为：0
- “ABC”的前缀为[A，AB]，后缀为[BC，C]，相等的前缀后缀长度为：0
- “ABCA”的前缀为[A，AB，ABC]，后缀为[BCA，CA，A]，相等的前缀后缀为“A”，长度为：1
- “ABCAB”的前缀为[A，AB，ABC，ABCA]，后缀为[BCAB，CAB，AB，B]，相等的前缀后缀为“AB”，长度为2
字符串匹配举例一：
文本串S=“abcdefgab........”，模式串P=“abcdex”，定位模式串P在文本串S中的位置：
我们约定 i 是指向S某个字符位置的索引，j 是指向模式串P某个字符位置的索引。
image.png
上图是传统暴力匹配的方式。
1、从上图的流程中可知，模式串“abcdex”中所有的字符都不相等。当i=5时，P[5]和S[5]出现匹配失败，此时可推断出：P[0]和S[1]、S[2]、S[3]、S[4]也一定不同，所以第2、3、4、5步的判断都是多余的。
2、从上图的流程中，通过向右滑动模式串，可发现的规律如下：[这是我想清楚的最主要的原因]
第二步比较的是：S串的：bcde 和 P串的：abcd 【本质：字符串“abcde”，长度为4的前缀和长度为4的后缀进行比较】
第三部比较的是：S串的：ced 和 P串的：abc 【本质：字符串“abcde”，长度为3的前缀和长度为3的后缀进行比较】
第四步比较的是：S串的：de 和 P串的：ab 【本质：字符串“abcde”，长度为2的前缀和长度为2的后缀进行比较】
第五步比较的是：S串的：e 和 P串的：a 【本质：字符串“abcde”，长度为1的前缀和长度为1的后缀进行比较】
事实上KMP的算法精髓是：在指定字符串中，有相等前缀和后缀时，才会考虑把模式串 的前缀滑动 和 后缀重叠的位置上，从而继续校验剩下的字符是否相等；当然如果没有相等的前缀和后缀，就无须比较，因为没有能覆盖重叠的地方，j赋值为0，模式串直接移动到 和 i 的位置进行下一轮比较；如果指定的字符串相等的前缀和后缀有多个，例如：ababa，的前缀有：[a,ab,aba,abab]，后缀有：[baba,aba,ba,a]，相等的前缀后缀为：aba 和 a，此时要选择让模式串滑动到最长的相等前缀后缀上，因为这样模式串向右移动的最少，才不至于漏掉了更多应该比较的位置。
字符串匹配举例二：
文本串S=“abcabcabc........”，模式串P=“abcabx”，定位模式串P在文本串S中的位置：
我们约定 i 是指向S某个字符位置的索引，j 是指向模式串P某个字符位置的索引。
image.png
当匹配到i=5时，S[5]=c；P[5]=x，匹配失败。x之前的字符串为：“abcab” ，它的最长相等前缀后缀为ab，长度为2，则直接让j=2 指向c（相等于模式串向右滑动3 = [5-2] 位），继而进行下一次比较。
KMP的算法特征是保证 i 索引不回溯，通过修改 j 的值，在一定程度上提交算法效率。具体的到底模式串向右滑动多少，j值取多少，只跟模式串有关。主要是算出模式串中每个字符的最长相等前缀和后缀 组成的一个数组 next，从而决定如何滑动。
next数组举例说明：
| 模式串 | a | b | a | b |
|---|---|---|---|---|
| next | 0 | 0 | 1 | 2 |
next数组中每一位代表的是最长相等前缀后缀长度。
算法的实现
public static int[] kmpNext(String dest){
int[] next=new int[dest.length()];
next[0]=0;
//开始推出next
for(int i=1,j=0;i<dest.length();i++){
//3：这一部分是整个代码里最难理解的。
while(j>0 && dest.charAt(j) != dest.charAt(i)){
j=next[j-1];
}
//1
if(dest.charAt(i)==dest.charAt(j)){
j++;
}
//2
next[i]=j;
}
return next;
}
public static int kmp(String str,String dest,int[] next){
for(int i=0,j=0;i<str.length();i++){
while(j>0 && str.charAt(i) != dest.charAt(j)){
j=next[j-1];
}
if(str.charAt(i)==dest.charAt(j)){
j++;
}
if(j==dest.length()){//结束
return i-j+1;
}
}
return 0;
}
理解了基本原理完成了60%对于算法的掌握，kmpNext方法很直观：为模式串中每一个字符算出对应的最长相等前缀后缀长度，但是当我第一次看到代码的时候，我是懵逼的，尤其是第3条注释：
//3：这一部分是整个代码里最难理解的。
while(j>0 && dest.charAt(j) != dest.charAt(i)){
j=next[j-1];
}
下面就用一个举例来说明 kmpNext方法的实现思路：
假设模式串：ABCABCABF。
我们知道next代表的是每个字符的最长相等前缀和后缀长度。那kmpNext中，什么代表前缀，什么代表后缀呢? 答案是：j > 0时，所划过的字符是 “前缀”，i 承担着记录“后缀的”工作。 一旦发现 模式串中有哪个字符 跟第一个字符相等，此时就代表了有相同前缀后缀了，就要进行记录了。接下来着重说明最难理解的这部分代码逻辑：
image.png
当 i = 8 时， j = 5。此时 i 对应的字符为“F”，j 对应的字符为“C”
此时next = [0,0,0,1,2,3,4,5, ]，就差算出 “F” 位置的 值了。
假如 P[8] = P[5]，此时皆大欢喜，“F”位置就可以填6了。
可现实是：此时P[i] 不等于 P[j]，那么接下来该怎么处理呢？
常理来看，我们应该在剩下的ABDAB中看是不是有 BCABF 相等的前缀和后缀。
比较：ABCAB（前缀） 和 BCABF（后缀）
注意：【先抛开最后一位的比较不谈，因为只有前几位相等，最后一位才有比较的必要性，否则，直接不用比了，本质----->ABCA 和 BCAB 是否相等】
比较：ABCA（前缀） 和 CABF（后缀）----->【本质：ABC 和 CAB 是否相等】
比较：ABC（前缀） 和 ABF（后缀）----->【本质：AB 和 AB 是否相等】
比较：AB（前缀） 和 BF（后缀）----->【本质：A 和 B 是否相等】
上边的比较看出来了吧，这个过程就是其实就是 模式串“ABDAB” 的所有相等长度前缀和后缀比较的过程。也是说，如果ABCAB有最长相等前缀和后缀，才会考虑比较，如果没有，直接 j = 0，i= 8，开始跳出while循环，执行接下来的判断了。
因为此时“ABCAB”的所有值next已经算出来了，所以 next[j - 1]就是 j 此时之前一位的字符串“ABCAB”的next值：2，也就是说有2位相等的前缀和后缀，所以我们想 ABC 和 ABF 才有可能相等，此时让 j = next[j - 1] = 2 指向C，i = 8，指向F， 接下来再进行判断。 按照此思路，一直到 j = 0了，跳出注释3的while循环，此时就当之前没有发生过任何事情一样，一切归零了，开始了新一轮的比较。
总结：其实注释3的代码就是，j之前一直匹配的上，当发生匹配不上的时候，就看j之前的串里有没有能匹配上的，但是根据next的原理，不用一个一个找，直接使用 前缀、后缀匹配的思路就行。 KMP算法使用了前缀、后缀的思路算法，求解next数组的时候也用到了 前缀、后缀的思路。
注意：求next数组的过程中，i 也是不回溯的。
以上是我看了很多文章、书籍之后，想明白的一点这个算法是如何想出来的，或者是还原算法的流程，让更多人能够更好的理解吧。 理解这个算法最重要的是要想象 模式串像一把尺子一样，向右滑动，在滑动的过程中是用模式串的前缀和后缀进行匹配。这篇文章讲的不全，只是写出来让我醍醐灌顶理解的瞬间，特此记录下来。
参考：
字符串匹配KMP算法
《大话数据结构》
