KMP算法是解決字符串匹配的常用算法之一，也就是在主串（比如aabbccdd）中的子串（bc）定位問題。子串稱為P益眉，如果它在一個主串稱為T中出現(xiàn)袭灯，就返回它的具體位置刺下，我們先來看看普通的字符串匹配是怎么做的
最基礎(chǔ)的匹配
思路：從左到右一個個匹配，如果這個過程中有某個字符不匹配稽荧，將子串向右移動一位橘茉，繼續(xù)從左到右一一匹配。
當(dāng)匹配到如圖第四個字符位置后蛤克，匹配失敗捺癞，子串后移，繼續(xù)匹配
第一位匹配失敗构挤，繼續(xù)后移...
直到匹配成功
[圖片上傳失敗...(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]) { // 當(dāng)兩個字符相同髓介，就比較下一個
i++;
j++;
} else {
i = i - j + 1; // 一旦不匹配，i后退
j = 0; // j歸0
}
}
if (j == p.length) {
return i - j;
} else {
return -1;
}
}
}
這種方式是效率最低筋现，匹配次數(shù)最多的情況唐础，接下來看KMP的解決思路
KMP中的PMT
KMP在遇到下圖位置時，不會很無腦的把子串的j移動到第0位矾飞，主串的i移動到第1位一膨，然后進(jìn)行T[i]==P[j]的比較
[圖片上傳失敗...(image-1dbb87-1548667452278)]
因為從圖上可以看得出后移一位后子串前三位（ABC）和主串的T[1-4]（BCA）肯定是不匹配的，無需白白浪費這幾次比較洒沦，最好應(yīng)該是直接讓i不變豹绪，j==0，如下圖
從這里開始匹配申眼，省去了前面的幾次無用匹配瞒津。
KMP思想：利用前面匹配的信息，保持i指針不變括尸，通過修改j指針巷蚪，讓子串盡量地移動到有效的位置。
整個KMP的重點就在于當(dāng)某一個字符與主串不匹配時濒翻，我們應(yīng)該知道j指針要移動到哪屁柏？
先用肉眼來看一下規(guī)律：
如圖：C和D不匹配了，我們要把j移動到哪有送？顯然是第1位淌喻。為什么？因為前面有一個A相同可以用：
再看一種：
可以把j指針移動到第2位雀摘，因為前面有兩個字母是一樣的：
我們可以看出來似嗤，匹配失敗的時候，j變?yōu)閗,j前面的的n個字符等于子串開頭到k位置的n個字符的值
即：P[0 ~ k-1] == P[j-k ~ j-1]
這時我們發(fā)現(xiàn)規(guī)律了届宠，其實就是要求當(dāng)前j之前的字符串也就是ABCAB它的首尾對稱的長度最大長度也就是PMT值烁落。
PMT中的值是字符串的前綴集合與后綴集合的交集中最長元素的長度乘粒。
例如，對于”aba”伤塌，它的前綴集合為{”a”, ”ab”}灯萍，后綴集合為{”ba”, ”a”}。
兩個集合的交集為{”a”}每聪，
那么長度最長的元素就是字符串”a”了旦棉，長度為1，所以對于”aba”而言药薯，它在PMT表中對應(yīng)的值就是1绑洛。
再比如，對于字符串”ababa”童本，它的前綴集合為{”a”, ”ab”, ”aba”, ”abab”}真屯，
它的后綴集合為{”baba”, ”aba”, ”ba”, ”a”}，
兩個集合的交集為{”a”, ”aba”}穷娱，其中最長的元素為”aba”绑蔫，長度為3。
所以上面最后一個圖的情況下泵额，j位置之前的字符串的PMT值為2配深，所以j的值變成2。
KMP之next數(shù)組
那么好了接下來核心就是求得P串每個下標(biāo)元素對應(yīng)的k值即可嫁盲，因為在P的每一個位置都可能發(fā)生不匹配篓叶，我們要計算每一個位置j對應(yīng)的k，所以用一個數(shù)組next來保存羞秤，next[j] = k澜共，表示當(dāng)T[i] != P[j]時，j應(yīng)該變?yōu)閗锥腻。
求next數(shù)組代碼如下
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，當(dāng)j為0時母谎，已經(jīng)無法后退了所以設(shè)置為-1初始化值瘦黑，當(dāng)j為1時，它的前面只有下標(biāo)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;
因為當(dāng)在p[j-1]處匹配失敗后，j-1變?yōu)閗-1咬扇，從k-1處重新開始匹配甲葬，原因就是他們共同有一個前綴A，所以當(dāng)p[j] == p[k]后懈贺，他們就擁有了前綴AB所以k++经窖；
第二種p[j] != p[k]
此時代碼是：k = next[k];原因看下圖
像上邊的例子坡垫，我們已經(jīng)不可能找到[ A，B画侣，A冰悠，B ]這個最長的后綴串了，但我們還是可能找到[ A配乱，B ]溉卓、[ B ]這樣的前綴串的。所以這個過程就像在定位[ A搬泥，B桑寨，A，C ]這個串忿檩，當(dāng)C和主串不一樣了（也就是k位置不一樣了）尉尾，那當(dāng)然是把指針移動到next[k]。
有了next數(shù)組之后就一切好辦了休溶，我們可以動手寫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]) { // 當(dāng)j為-1時代赁，要移動的是i，當(dāng)然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改進(jìn)
KMP算法是存在缺陷的兽掰，來看一個例子：比如主串是aaaabcde芭碍，子串是aaaaax，next值為012345孽尽，當(dāng)i=5時窖壕，如下圖：
我們發(fā)現(xiàn)，當(dāng)中的②③④⑤步驟杉女，其實是多余的判斷瞻讽。由于子串的第二、三熏挎、四速勇、五位置的字符都與首位的“a”相等，那么可以用首位next[1]的值去取代與它相等的字符后續(xù)next[j]的值坎拐，這是個很好的辦法烦磁。因此我們對求next函數(shù)進(jìn)行了改良。
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]) { // 當(dāng)兩個字符相等時要跳過
next[j] = next[k];
} else {
next[j] = k;
}
} else {
k = next[k];
}
}
return next;
}
}
