>> KMP算法詳解招盲，小白都懂的講解，歡迎交流算谈，邊聽(tīng)歌邊看吧
概念解釋
Knuth-Morris-Pratt算法料滥，簡(jiǎn)稱(chēng)KMP算法然眼，是一種字符串匹配算法。它以三個(gè)發(fā)明者命名葵腹，起頭的那個(gè)K就是著名科學(xué)家Donald Knuth高每。
KMP幾年前學(xué)過(guò)，當(dāng)時(shí)學(xué)的也忘得差不多了践宴，到了今天鲸匿，又接觸到KMP，于是決定以最通俗形象的描述來(lái)講解一下KMP阻肩。
字符串匹配
有一個(gè)主字符串S带欢，長(zhǎng)度為n ，和模式串P烤惊，長(zhǎng)度為k乔煞，k>0并且k<=n，我們需要在主串S中找出第一個(gè)P（這里說(shuō)第一個(gè)P是比較嚴(yán)謹(jǐn)?shù)钠馐遥驗(yàn)橛锌赡躍中有多個(gè)P渡贾，我們只要找到第一個(gè)即可），并輸出P在S中的第幾位雄右。
比如主串S為ABCABCABD空骚，模式串P為ABCABD，那么我們應(yīng)該應(yīng)該輸出3（序號(hào)是從0開(kāi)始的）
序號(hào)：0｜1 ｜2｜3｜4 ｜5｜6 ｜7｜8
S：? ? A｜B｜C｜A｜B｜C｜A｜B｜D
P：? ? ? ? ? ? ? ? ? ? ? A｜B｜C｜A | B? | D
常規(guī)思路-暴力匹配
在講KMP之前擂仍，先按照正常思路來(lái)解囤屹，要想找到P，我們最容易想到的算法就是從左到右依次遍歷主串S逢渔，依次和模式串P比較牺丙，直到找到完全匹配P的為止。
也就是說(shuō)，我們先假設(shè)P在S的第i位冲簿，(i>=0粟判，并且i <= n-k，這個(gè)范圍懂不峦剔？因?yàn)槿绻鹡-i<k档礁，那么肯定和P是不匹配的，長(zhǎng)度都不對(duì)吝沫，怎么匹配呢)呻澜。即S[i] == P[0] , S[i+1] == P[1] , ... , S[i+k] == P[k], 所以我們先假設(shè)i為0，然后開(kāi)始比較惨险，如果匹配失敗羹幸，則i++；直到找到完全和P匹配的辫愉，則輸出i栅受，如果i>n-k捞挥，則表示S中不存在P包斑，輸出-1.
下面實(shí)例形象說(shuō)明，有兩個(gè)數(shù)組剖煌，S和P
i = 0;
S序號(hào)? 0｜1 ｜2｜3｜4 ｜5｜6 ｜7｜8
S：? ? ?A｜B｜C｜A｜B｜C｜A｜B｜D
P：? ? ?A｜B｜C｜A | B?|??D
P序號(hào)? 0｜1 ｜2｜3 | 4? | 5
1痰腮、S[0] == P[0] ?而芥，相等
2、繼續(xù)比較S[1]==P[1] ?膀值，依然相等
棍丐。。沧踏。（省略2骄酗、3、4的比較）悦冀。趋翻。。
3盒蟆、繼續(xù)比較S[5]==P[5] ?踏烙，結(jié)果不相等
上面我們是從S[0]開(kāi)始和P[0]比較的，并且比較失敗历等，這時(shí)候我們要嘗試P[0]和S[1]比較
也就是 i=1;
序號(hào)：0｜1 ｜2｜3｜4 ｜5｜6 ｜7｜8
S：? ? A｜B｜C｜A｜B｜C｜A｜B｜D
P：? ? ? ? ? A｜B｜C｜A | B? | D
P序號(hào)? ? ? ?0｜1 ｜2｜3 | 4? | 5
1讨惩、S[1] == P[0] ? A和B顯然不等，匹配失敗
那么我們S的指針繼續(xù)指向下一個(gè)寒屯，P[0]和S[2]比較荐捻，即i=2黍少；發(fā)現(xiàn)還是不等，相同的操作就不多說(shuō)了处面，直接跳到 i=3厂置；
序號(hào)：0｜1 ｜2｜3｜4 ｜5｜6 ｜7｜8
S：? ? A｜B｜C｜A｜B｜C｜A｜B｜D
P：????????????? ? ? ? ? A｜B｜C｜A??| B | D
P序號(hào)? ? ? ?????????????0｜1 ｜2｜3 | 4? | 5
我們發(fā)現(xiàn)S[3]=P[0], S[4]=P[1],S[5]=P[2], S[6]=P[3]，?S[7]=P[4]魂角，?S[8]=P[5]昵济，匹配成功，輸出3野揪，結(jié)束访忿。
下面看代碼
//暴力匹配
void?BF(char*S,?char*P) {
? ? unsigned?long?sLen = strlen(S); //S的長(zhǎng)度
? ? unsigned?long?pLen = strlen(P); //P的長(zhǎng)度
? ? int?position = -1; //匹配的位置，默認(rèn)是-1
? ? int?i =0, j =0;
? ? while(i <= sLen - pLen) {
? ? ? ? while(j < pLen) {
? ? ? ? ? ? if(P[j] == S[i + j]) {? //如果相等斯稳，則繼續(xù)比較下一位
? ? ? ? ? ? ? ? j++;
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? i++; //如果不等則從下一位開(kāi)始比較
? ? ? ? ? ? ? ? j =0;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? if(j == pLen) {
? ? ? ? ? ? ? ? position = i; //如果j == pLen海铆，說(shuō)明匹配完了并且都對(duì)了，也就是找到了
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if(position > -1) { //說(shuō)明已經(jīng)找到了
? ? ? ? ? ? break;
? ? ? ? }
? ? }
? ? printf("P at %d\n",position);
}
KMP登場(chǎng)
暴力匹配既然可以解決匹配問(wèn)題挣惰，而且還簡(jiǎn)單卧斟，為什么需要KMP呢？顯然通熄，是為了優(yōu)化唆涝，暴力匹配的時(shí)間復(fù)雜度是O(n*n)找都，優(yōu)化空間還是有的唇辨。
還是剛才的例子，我們一起來(lái)看看哪里可以?xún)?yōu)化能耻。
S序號(hào)? 0｜1 ｜2｜3｜4 ｜5｜6 ｜7｜8
S：? ? ?A｜B｜C｜A｜B｜C｜A｜B｜D
P：? ? ?A｜B｜C｜A?|?B??|?D
P序號(hào)? 0｜1 ｜2｜3 | 4? | 5
當(dāng)我們比較到S[5] 和P[5]的時(shí)候赏枚，按照暴力匹配算法，下一步是i=1晓猛，也就是S[1]和P[0]比較饿幅，但是我們真的有必要把S[1]和P[0]比較嗎？
我們給模式串來(lái)個(gè)特寫(xiě)? ?A｜B｜C｜A?|?B??|?D
發(fā)現(xiàn)了這個(gè)串有個(gè)特點(diǎn)戒职，就是有兩個(gè)AB栗恩，如果當(dāng)D匹配失敗的時(shí)候，說(shuō)明主串前兩個(gè)必定是AB洪燥，要不也不需要再和D匹配了磕秤。既然主串前兩個(gè)是AB，而且模式串第一個(gè)字母和第二個(gè)字母也剛好是AB捧韵，那么就無(wú)需再重復(fù)比較了市咆。細(xì)品這兩句話，多讀幾遍再来，懂了再往下看蒙兰。
懂了之后，我們?cè)倮^續(xù)往下看，
那么i還有必要為1嗎搜变？沒(méi)必要了采缚，i可以直接保留為5，而j=2 ( j 為P的下標(biāo) ) , 因?yàn)槲覀冎繱[3]S[4]為AB痹雅，P[0]P[1]也是AB仰担，所以可以直接把S[5]和P[2]比較。
S序號(hào)? 0｜1 ｜2｜3｜4 ｜5｜6 ｜7｜8
S：????A｜B｜C｜A｜B｜C｜A?|?B｜D
P：? ? ? ? ? ? ? ? ? ? ??A｜B｜C｜A?|?B?|?D
P序號(hào)? ? ? ? ? ? ? ? ? ?0｜1 ｜2｜3 | 4? | 5
由此我們可以看出绩社，KMP的特定有
1摔蓝、i不需要回退，（對(duì)比暴力算法愉耙，i每次匹配失敗都要回退到原來(lái)的起點(diǎn)+1）
2贮尉、j不一定要重0開(kāi)始，只是不一定
這樣就省了不少時(shí)間朴沿。
那么問(wèn)題來(lái)了猜谚，當(dāng)我們遇到不匹配的字符的時(shí)候，我們?nèi)绾未_定模式串應(yīng)該回退到哪赌渣？
這就是KMP里的重點(diǎn)了魏铅。
next數(shù)組
在KMP中，有個(gè)next數(shù)組坚芜，它的長(zhǎng)度和模式串的長(zhǎng)度一樣览芳，記錄著對(duì)應(yīng)字符匹配失敗時(shí)應(yīng)該回退到哪一個(gè)。
在求next數(shù)組前鸿竖，先了解一個(gè)概念沧竟，叫前綴后綴最長(zhǎng)公共元素長(zhǎng)度。
前綴：字符串前面的子串缚忧，但不包含最后一個(gè)字符悟泵。比如字符串a(chǎn)bcd，前綴有 a, ab,abc
后綴：字符串后面的子串闪水，但不包含第一個(gè)字符糕非。比如字符串a(chǎn)bcd，后綴有 d,cd,bcd
前綴后綴最長(zhǎng)公共元素：一個(gè)字符串中的所有前綴和后綴中球榆，相同且最長(zhǎng)的一個(gè)朽肥，比如abcd中，不存在前綴后綴最長(zhǎng)公共元素芜果。abcdabc中前綴后綴最長(zhǎng)公共元素是abc鞠呈。ababa的是aba。
為啥要介紹這個(gè)概念呢右钾？因?yàn)閚ext數(shù)組里面的值蚁吝，就是當(dāng)前字符之前的字符串中的最長(zhǎng)相同前綴后綴長(zhǎng)度旱爆。
P：? ? ? ? ? ?A｜B｜C｜A?|?B?|?D
next:? ? ? ? ?0 |? 0? | 0? | 0 |? 1? | 2?
模式串ABCABD對(duì)應(yīng)的next數(shù)組就是000012；
這個(gè)next數(shù)組的值為什么是當(dāng)前字符之前的字符串中的最長(zhǎng)相同前綴后綴長(zhǎng)度呢窘茁？對(duì)應(yīng)下面的表格一起看怀伦，next數(shù)組本質(zhì)是記錄當(dāng)前字符匹配失敗時(shí)應(yīng)該回退的位置，當(dāng)?shù)谝粋€(gè)A匹配失敗時(shí)山林，顯然只能回退到自己本身房待，當(dāng)B匹配失敗，前面并無(wú)公共元素驼抹，所以也是回退到0桑孩，CA同理，當(dāng)?shù)诙€(gè)B匹配時(shí)候時(shí)框冀，因?yàn)榍懊嬗泄苍谹流椒，所以A不需要再比較了，回退到第一個(gè)B的位置也就是1明也，后面的同理宣虾。
下面表格表示每個(gè)字符位置對(duì)應(yīng)的最長(zhǎng)前后綴公共元素長(zhǎng)度計(jì)算過(guò)程，粗體表示前后綴公共元素温数。
talk is cheap, show me the code绣硝，下面直接看看代碼是如何實(shí)現(xiàn)這個(gè)過(guò)程的
//求next數(shù)組，next數(shù)組表示回退的值撑刺，而不是最大長(zhǎng)度鹉胖，若是把next數(shù)組整體左移一位，則表示最大長(zhǎng)度了
void?initNext(char*P,?int*next) {
? ? unsigned?long?pLen =strlen(P);//P的長(zhǎng)度
? ? //前兩個(gè)肯定沒(méi)有除了本身之外的公共元素猜煮，所以直接給0
? ? if(pLen >0) {
? ? ? ? next[0] =0;
? ? }
? ? if(pLen >1) {
? ? ? ? next[1] =0;
? ? }
? ? intj =1;//P[j]表示后綴
? ? inti =0;//P[i]表示前綴
? ? while(j < pLen) {
? ? ? ? if(P[j] == P[i]) {//如果后綴和前綴相等
? ? ? ? ? ? j++;//則都加一次员，繼續(xù)比較下一位
? ? ? ? ? ? i++;
? ? ? ? ? ? next[j] = next[j-1] + 1;//這里的j是加1之后的败许，所以下一個(gè)next的值是前面字符串的前后綴的最長(zhǎng)公共元素長(zhǎng)度王带，這里有點(diǎn)遞進(jìn)的感覺(jué)，前面的長(zhǎng)度+1是因?yàn)橛终业搅艘粋€(gè)相等的前后綴
? ? ? ? }else?if(i ==0){//如果前綴已經(jīng)是0市殷，則找下一個(gè)后綴
? ? ? ? ? ? j ++;
? ? ? ? }else {//如果匹配失敗愕撰，則回退
? ? ? ? ? ? i = next[i];
? ? ? ? }
? ? }
? ? return;
}
這段代碼可能比較難理解，其實(shí)是利用了遞進(jìn)關(guān)系醋寝，首先搞挣，需要注意，next是回退的位置音羞，而不是最長(zhǎng)的長(zhǎng)度囱桨，也可以理解為最長(zhǎng)長(zhǎng)度減一，其實(shí)就差了一個(gè)1嗅绰。next[0] 和 next[1]肯定是0舍肠，因?yàn)閚ext[0]只有一個(gè)字符搀继，不存在前后綴，也就是說(shuō)翠语，一旦P[0]匹配失敗了叽躯，那也只能回退到P[0]，所以是0肌括。next[1]為什么也是0? 從匹配的角度來(lái)解釋?zhuān)僭O(shè)P[1]匹配失敗点骑，也只能向后回退，后面只有P[0]了谍夭。從前后綴的角度來(lái)解釋?zhuān)驗(yàn)閚ext[1]只有兩個(gè)字符黑滴，那么前綴就是P[0]，后綴是P[1]紧索，最大長(zhǎng)度要么是1跷跪，要么是0，那么回退位置是最大長(zhǎng)度減一齐板，那么就是0或-1吵瞻，不能為負(fù)數(shù)（數(shù)組下標(biāo)沒(méi)有負(fù)數(shù)），所以只能是0甘磨。
那么從next[2]之后的值橡羞，都存在一個(gè)關(guān)系，那就是
如果匹配到了一個(gè)相等的相等的前后綴济舆，那么next[j] = next[j-1] + 1卿泽。
栗子：
index:? ? ?0? ?| 1? | 2? ?| 3? | 4 | 5
P：? ? ? ? ??A｜B｜C｜A?|?B?|?D
next:? ? ? ? ?0 |? 0?|? 0? |? 0 |? 0 | 0??
1、初始化所有的next為0
2滋觉、先比較最短的子串 AB （P[0]和P[1]）
3签夭、AB不等，則比較AC（P[0]和P[2]）
4椎侠、AC不等第租，則比較AA，（P[0]和P[3]）
5我纪、AA相等慎宾，則next[4] = next[3] + 1 ，也就是next[4] = 1;
index:? ? ?0? ?| 1? | 2? ?| 3? | 4 | 5
P：?????????A｜B｜C｜A?|?B??|?D
next:? ? ? ? ?0 |? 0?|? 0? |?0 |? 1 | 0
6浅悉、比較B和B（ P[1]和P[4]）
7趟据、BB? 相等，則next[5] = next[4] + 1 术健，也就是next[5] = 2;
index:? ? ?0? ?| 1? | 2? ?| 3? | 4 | 5
P：? ? ? ? ?A｜B｜C｜A?|B??|D
next:? ? ? ? 0 |? 0?|? 0? |?0 |? 1 | 2
8汹碱、比較C和D（ P[2]和P[5]）
9、CD不等荞估，結(jié)束
KMP算法
next數(shù)組已經(jīng)求出來(lái)了咳促，接下來(lái)就可以寫(xiě)KMP算法了
主要思路就是 1色难、主串S開(kāi)始遍歷和模式串P比較? 2、如果遇到匹配失敗等缀，則模式串回退到next[j]位置? 3枷莉、如果遇到不匹配并且模式串本身就在0位置，則主串往下移動(dòng)一位
代碼就是
//KMP
void?KMP(char*S,?char*P) {
? ? unsigned?long?pLen =strlen(P);
? ? unsigned?long?sLen =strlen(S);
? ? int*next = (int*)malloc(pLen *sizeof(int));
? ? initNext(P, next);
? ? inti =0;//主串的下標(biāo)
? ? intj =0;//模式串下標(biāo)
? ? int?position = -1;
? ? while(i <= sLen - pLen + j ) {
? ? ? ? if(S[i] == P[j]) {
? ? ? ? ? ? if(j == pLen -1) {//如果P已經(jīng)匹配結(jié)束了尺迂，則表示找到了
? ? ? ? ? ? ? ? position = i - j;//計(jì)算出第一個(gè)匹配的位置
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? //右移一位比較
? ? ? ? ? ? i++;
? ? ? ? ? ? j++;
? ? ? ? }elseif(j ==0) {
? ? ? ? ? ? i++;//模式串是0笤妙，則只需移動(dòng)主串
? ? ? ? }else{
? ? ? ? ? ? j = next[j];//回退
? ? ? ? }
? ? }
? ? printf("KMP: P at %d\n",position);
}
其實(shí)求next的算法和KMP的算法是不是很像
