KMP算法是解決字符串匹配的常用算法之一，也就是在主串（比如aabbccdd）中的子串（bc）定位問題。子串稱為P，如果它在一個主串稱為T中出現，就返回它的具體位置，我們先來看看普通的字符串匹配是怎麼做的
最基礎的匹配思路：從左到右一個個匹配，如果這個過程中有某個字符不匹配，將子串向右移動一位，繼續從左到右一一匹配。
當匹配到如圖第四個字符位置後，匹配失敗，子串後移，繼續匹配
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;
j = 0;
}
}
if (j == p.length) {
return i - j;
} else {
return -1;
}
}
}
這種方式是效率最低，匹配次數最多的情況，接下來看KMP的解決思路
KMP中的PMTKMP在遇到下圖位置時，不會很無腦的把子串的j移動到第0位，主串的i移動到第1位，然後進行T[i]==P[j]的比較
KMP思想：利用前面匹配的信息，保持i指針不變，通過修改j指針，讓子串儘量地移動到有效的位置。
整個KMP的重點就在於當某一個字符與主串不匹配時，我們應該知道j指針要移動到哪？
先用肉眼來看一下規律：
這時我們發現規律了，其實就是要求當前j之前的字符串也就是ABCAB它的首尾對稱的長度最大長度也就是PMT值。
PMT中的值是字符串的前綴集合與後綴集合的交集中最長元素的長度。
例如，對於」aba」，它的前綴集合為，後綴集合為。
兩個集合的交集為，
那麼長度最長的元素就是字符串」a」了，長度為1，所以對於」aba」而言，它在PMT表中對應的值就是1。
再比如，對於字符串」ababa」，它的前綴集合為，
它的後綴集合為，
兩個集合的交集為，其中最長的元素為」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]時，有next[++j] = ++k;
因為當在p[j-1]處匹配失敗後，j-1變為k-1，從k-1處重新開始匹配，原因就是他們共同有一個前綴A，所以當p[j] == p[k]後，他們就擁有了前綴AB所以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]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == p.length) {
return i - j;
} else {
return -1;
}
}
}
KMP算法是存在缺陷的，來看一個例子：比如主串是aaaabcde，子串是aaaaax，next值為012345，當i=5時，如下圖：
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;
}
}