要解決什么問題
要解決的問題就是在字符串（也叫主串）中的模式（pattern）定位問題撕贞。說簡單點(diǎn)就是我們平時常說的關(guān)鍵字搜索硼砰。模式串就是關(guān)鍵字（接下來稱它為P）菲驴，如果它在一個主串（接下來稱為T）中出現(xiàn)凄杯，就返回它的具體位置悬荣，否則返回-1（常用手段）菠秒。
約定
數(shù)組下標(biāo)從0開始
為什么會有KMP算法
因?yàn)楸┝δＪ阶址ヅ湫阅芴盍恕Ｄ敲聪瓤匆幌卤┝δＪ绞鞘裁礃拥陌伞?/p>
暴力模式
以如下為例
從左到右一個個匹配氯迂，如果這個過程中有某個字符不匹配践叠，就跳回去，將模式串向右移動一位
假如初始化的時候?yàn)橄旅娴膱D
之后我們只需要比較i指針指向的字符和j指針指向的字符是否一致嚼蚀。如果一致就都向后移動禁灼，如果不一致，如下圖：
A和E不相等轿曙，那就把i指針移回第1位（假設(shè)下標(biāo)從0開始）弄捕，j移動到模式串的第0位，然后又重新開始這個步驟：
/**
* 暴力破解法
* @param ts 主串
* @param ps 模式串
* @return 如果找到导帝，返回在主串中第一個字符出現(xiàn)的下標(biāo)守谓，否則為-1
*/
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;
}
}
上面的這種情況還是比較理想的情況分飞，我們最多也就多比較了三次。但假如是在主串“SSSSSSSSSSSSSA”中查找“SSSSB”睹限，比較到最后一個才知道不匹配譬猫，然后i回溯，這個的效率是顯然是最低的羡疗。
KMP上場
繼續(xù)回到上面的例子染服。如果是人為來尋找的話，肯定不會再把i移動回第1位叨恨，因?yàn)橹鞔ヅ涫〉奈恢们懊娉说谝粋€A之外再也沒有A了柳刮。移動過去肯定也是不匹配的！有一個想法痒钝，i可以不動秉颗，我們只需要移動j即可，如下圖：
KMP的思想就是“利用已經(jīng)部分匹配這個有效信息送矩，保持i指針不回溯蚕甥，通過修改j指針，讓模式串盡量大的移動到有效的位置栋荸」交常”
所以凭舶，整個KMP的重點(diǎn)就在于當(dāng)某一個字符與主串不匹配時，我們應(yīng)該知道j指針要移動到哪爱沟？接下來就來尋找規(guī)律帅霜。
接下來我們自己來發(fā)現(xiàn)j的移動規(guī)律：
如圖：C和D不匹配了，我們要把j移動到哪呼伸？顯然是第1位身冀。為什么？因?yàn)榍懊嬗幸粋€A相同袄ㄏ怼：
另外一個例子也是同樣的情況
可以把j指針移動到第2位搂根，因?yàn)榍懊嬗袃蓚€字母是一樣的：
至此我們可以大概看出一點(diǎn)端倪，當(dāng)匹配失敗時奶浦，j要移動的下一個位置k兄墅。存在著這樣的性質(zhì)：最前面的k個字符和j之前的最后k個字符是一樣的踢星。
如果用數(shù)學(xué)公式來表示是這樣的
P[0 ~ k-1] == P[j-k ~ j-1]澳叉，這里要找到最大的k
通過下面的圖更好理解
當(dāng)P[0 ~ k-1] == P[j-k ~ j-1]的時候，為啥就可以直接將j移動到位置k了呢沐悦？下面給出理論證明：
當(dāng)T[i] != P[j]時
有 T[i-j ~ i-1] == P[0 ~ j-1]
又因?yàn)椋篜[0 ~ k-1] == P[j-k ~ j-1]
必然有：P[0 ~ k-1] == T[i-k ~ i-1]
這一段只是為了證明我們?yōu)槭裁纯梢灾苯訉移動到k而無須再比較前面的k個字符成洗。
接下來就是重點(diǎn)了，怎么求這個（這些）k呢藏否？因?yàn)樵赑的每一個位置都可能發(fā)生不匹配瓶殃，也就是說我們要計(jì)算每一個位置j對應(yīng)的k，所以用一個數(shù)組next來保存副签，next[j] = k遥椿，表示當(dāng)T[i] != P[j]時，j指針的下一個位置淆储。
先給出通用代碼
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;
}
推導(dǎo)思路
現(xiàn)在要始終記住一點(diǎn)冠场，next[j]的值（也就是k）表示，當(dāng)P[j] != T[i]時本砰，j指針的下一步移動位置碴裙。
【1】先來看第一個：當(dāng)j為0時，如果這時候不匹配点额，怎么辦舔株？
【2】如果是當(dāng)j為1的時候呢？
顯然还棱，j指針一定是后移到0位置的载慈。因?yàn)樗懊嬉簿椭挥羞@一個位置了~~~
【3】尋找一般規(guī)律
先看下面的圖：
請仔細(xì)對比這兩個圖。
我們發(fā)現(xiàn)一個規(guī)律：
當(dāng)P[k] == P[j]時珍手，
有next[j+1] == next[j] + 1
證明如下：
因?yàn)樵赑[j]之前已經(jīng)有P[0 ~ k-1] == p[j-k ~ j-1]
現(xiàn)在又有：P[k] == P[j]娃肿，
所以有：P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]咕缎，即：P[0 ~ k] == P[j-k ~ j]
因?yàn)槲覀兌x了：P[0 ~ k-1] == p[j-k ~ j-1]，對應(yīng)了next[j]==k
所以P[0 ~ k] == P[j-k ~ j]料扰，對應(yīng)了next[j+1]==k+1,又因?yàn)閗==next[j],
所以有：next[j+1]=next[j]+1
上面是P[k] == P[j]的情形凭豪，如果P[k] != P[j]呢？比如下圖所示：
如果你從代碼上看應(yīng)該是這一句：k = next[k];為什么是這樣子晒杈？
因?yàn)镻[k] != P[j]嫂伞，所以我們試圖從P[0~k-1]里面找一個最長前綴 P[0~r] == P[j-r~ j],為了達(dá)到這個目的，我們可以分成兩步操作：先從P[0~k-1] 里面找一個最長前綴P[0~r-1]拯钻，使它與最長后綴的p[j-r ~ j-1]部分相等帖努，然后再判斷p[r]是否和p[j]相等，如果p[r]==p[j]粪般，則有next[j+1]=r+1,否則拼余，k繼續(xù)回溯。現(xiàn)在來看這個r怎么算亩歹？
通過下面這個圖匙监，一下子就明白了
通過上圖可以看出：r==next[k]，因?yàn)槲覀兪褂胟代表回溯的位置小作，所以有k=next[k]
至此 可以給出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也要?dú)w0
i++;
j++;
} else {
// i不需要回溯了
// i = i - j + 1;
j = next[j]; // j回到指定位置
}
}
if (j == p.length) {
return i - j;
} else {
return -1;
}
}
