Knuth-Morris-Pratt 字符串查找算法，簡稱為 “KMP 算法”，常用于在一個(gè)文本串 S 內(nèi)查找一個(gè)模式串 P 的出現(xiàn)位置，這個(gè)算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年聯(lián)合發(fā)表，故取這三人的姓氏命名此算法。
下面先直接給出 KMP 的算法流程（如果感到一點(diǎn)點(diǎn)不適，沒關(guān)系，堅(jiān)持下，稍后會(huì)有具體步驟及解釋，越往后看越會(huì)柳暗花明 ?）：
很快，你也會(huì)意識(shí)到 next 數(shù)組各值的含義：代表當(dāng)前字符之前的字符串中，有多大長度的相同前綴后綴。例如，如果 next [j] = k，代表 j 之前的字符串中有最大長度為 k 的相同前綴后綴。
此也意味著在某個(gè)字符失配時(shí)，該字符對(duì)應(yīng)的 next 值會(huì)告訴你下一步匹配中，模式串應(yīng)該跳到哪個(gè)位置（跳到next [j] 的位置）。如果 next [j] 等于 0 或 -1，則跳到模式串的開頭字符，若 next [j] = k 且 k > 0，代表下次匹配跳到 j 之前的某個(gè)字符，而不是跳到開頭，且具體跳過了 k 個(gè)字符。
轉(zhuǎn)換成代碼表示，則是：
int KmpSearch(char* s, char* p)
{
int i = 0;
int j = 0;
int sLen = strlen(s);
int pLen = strlen(p);
while (i < sLen && j < pLen)
{
//①如果j = -1，或者當(dāng)前字符匹配成功（即S[i] == P[j]），都令i++，j++
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
//②如果j != -1，且當(dāng)前字符匹配失?。碨[i] != P[j]），則令 i 不變，j = next[j]
//next[j]即為j所對(duì)應(yīng)的next值
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
} 繼續(xù)拿之前的例子來說，當(dāng) S[10] 跟 P[6] 匹配失敗時(shí)，KMP 不是跟暴力匹配那樣簡單的把模式串右移一位，而是執(zhí)行第 ② 條指令：“如果 j != -1，且當(dāng)前字符匹配失?。?S[i] != P[j]），則令 i 不變，j = next[j]”，即 j 從 6 變到 2（后面我們將求得 P[6]，即字符 D 對(duì)應(yīng)的 next 值為 2），所以相當(dāng)于模式串向右移動(dòng)的位數(shù)為 j - next[j]（j - next[j] = 6-2 = 4）。
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3-1.png" alt="" />
向右移動(dòng) 4 位后，S[10] 跟 P[2] 繼續(xù)匹配。為什么要向右移動(dòng) 4 位呢，因?yàn)橐苿?dòng) 4 位后，模式串中又有個(gè)“AB”可以繼續(xù)跟 S[8]S[9] 對(duì)應(yīng)著，從而不用讓 i 回溯。相當(dāng)于在除去字符 D 的模式串子串中尋找相同的前綴和后綴，然后根據(jù)前綴后綴求出next 數(shù)組，最后基于 next 數(shù)組進(jìn)行匹配（不關(guān)心 next 數(shù)組是怎么求來的，只想看匹配過程是咋樣的，可直接跳到下文 3.3.4 節(jié)）。
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3-2.png" alt="" />
對(duì)于 P = p0 p1 ...pj-1 pj，尋找模式串 P 中長度最大且相等的前綴和后綴。如果存在 p0 p1 ...pk-1 pk = pj- k pj-k+1...pj-1 pj，那么在包含 pj 的模式串中有最大長度為 k+1 的相同前綴后綴。舉個(gè)例子，如果給定的模式串為“abab”，那么它的各個(gè)子串的前綴后綴的公共元素的最大長度如下表格所示：
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/321.jpg" alt="" />
比如對(duì)于字符串 aba 來說，它有長度為 1 的相同前綴后綴 a；而對(duì)于字符串 abab 來說，它有長度為 2 的相同前綴后綴ab（相同前綴后綴的長度為 k + 1，k + 1 = 2）。
next 數(shù)組考慮的是除當(dāng)前字符外的最長相同前綴后綴，所以通過第 ① 步驟求得各個(gè)前綴后綴的公共元素的最大長度后，只要稍作變形即可：將第 ① 步驟中求得的值整體右移一位，然后初值賦為 -1，如下表格所示：
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/322.jpg" alt="" />
比如對(duì)于 aba 來說，第 3 個(gè)字符 a 之前的字符串 ab 中有長度為 0 的相同前綴后綴，所以第 3 個(gè)字符 a 對(duì)應(yīng)的 next 值為 0；而對(duì)于 abab 來說，第 4 個(gè)字符 b 之前的字符串 aba 中有長度為 1 的相同前綴后綴 a，所以第 4 個(gè)字符 b 對(duì)應(yīng)的 next 值為 1（相同前綴后綴的長度為 k，k = 1）。
匹配失配，j = next [j]，模式串向右移動(dòng)的位數(shù)為：j - next[j]。換言之，當(dāng)模式串的后綴 pj-k pj-k+1, ..., pj-1 跟文本串 si-k si-k+1, ..., si-1 匹配成功，但 pj 跟 si 匹配失敗時(shí)，因?yàn)?next[j] = k，相當(dāng)于在不包含 pj 的模式串中有最大長度為 k 的相同前綴后綴，即 p0 p1 ...pk-1 = pj-k pj-k+1...pj-1，故令 j = next[j]，從而讓模式串右移 j - next[j] 位，使得模式串的前綴 p0 p1, ..., pk-1 對(duì)應(yīng)著文本串 si-k si-k+1, ..., si-1，而后讓 pk 跟 si 繼續(xù)匹配。如下圖所示：
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/323.jpg" alt="" />
綜上，KMP 的 next 數(shù)組相當(dāng)于告訴我們：當(dāng)模式串中的某個(gè)字符跟文本串中的某個(gè)字符匹配失配時(shí)，模式串下一步應(yīng)該跳到哪個(gè)位置。如模式串中在j 處的字符跟文本串在 i 處的字符匹配失配時(shí)，下一步用 next [j] 處的字符繼續(xù)跟文本串 i 處的字符匹配，相當(dāng)于模式串向右移動(dòng) j - next[j] 位。
接下來，分別具體解釋上述 3 個(gè)步驟。
如果給定的模式串是：“ABCDABD”，從左至右遍歷整個(gè)模式串，其各個(gè)子串的前綴后綴分別如下表格所示：
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/331.jpg" alt="" />
也就是說，原模式串子串對(duì)應(yīng)的各個(gè)前綴后綴的公共元素的最大長度表為（下簡稱《最大長度表》）：
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3311.jpg" alt="" />
因?yàn)槟Ｊ酱惺孜部赡軙?huì)有重復(fù)的字符，故可得出下述結(jié)論：
| 失配時(shí)，模式串向右移動(dòng)的位數(shù)為：已匹配字符數(shù) - 失配字符的上一位字符所對(duì)應(yīng)的最大長度值 |
下面，咱們就結(jié)合之前的《最大長度表》和上述結(jié)論，進(jìn)行字符串的匹配。如果給定文本串“BBC ABCDAB ABCDABCDABDE”，和模式串“ABCDABD”，現(xiàn)在要拿模式串去跟文本串匹配，如下圖所示：
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3320.png" alt="" />
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3321.png" alt="" />
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3322.png" alt="" />
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3323.png" alt="" />
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3324.png" alt="" />
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3325.png" alt="" />
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3326.png" alt="" />
通過上述匹配過程可以看出，問題的關(guān)鍵就是尋找模式串中最大長度的相同前綴和后綴，找到了模式串中每個(gè)字符之前的前綴和后綴公共部分的最大長度后，便可基于此匹配。而這個(gè)最大長度便正是 next 數(shù)組要表達(dá)的含義。
由上文，我們已經(jīng)知道，字符串“ABCDABD”各個(gè)前綴后綴的最大公共元素長度分別為：
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3331.jpg" alt="" />
而且，根據(jù)這個(gè)表可以得出下述結(jié)論
上文利用這個(gè)表和結(jié)論進(jìn)行匹配時(shí)，我們發(fā)現(xiàn)，當(dāng)匹配到一個(gè)字符失配時(shí)，其實(shí)沒必要考慮當(dāng)前失配的字符，更何況我們每次失配時(shí)，都是看的失配字符的上一位字符對(duì)應(yīng)的最大長度值。如此，便引出了 next 數(shù)組。
給定字符串“ABCDABD”，可求得它的 next 數(shù)組如下：
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3332.jpg" alt="" />
把 next 數(shù)組跟之前求得的最大長度表對(duì)比后，不難發(fā)現(xiàn)，next 數(shù)組相當(dāng)于“最大長度值” 整體向右移動(dòng)一位，然后初始值賦為 -1。意識(shí)到了這一點(diǎn)，你會(huì)驚呼原來 next 數(shù)組的求解竟然如此簡單：就是找最大對(duì)稱長度的前綴后綴，然后整體右移一位，初值賦為 -1（當(dāng)然，你也可以直接計(jì)算某個(gè)字符對(duì)應(yīng)的 next 值，就是看這個(gè)字符之前的字符串中有多大長度的相同前綴后綴）。
換言之，對(duì)于給定的模式串：ABCDABD，它的最大長度表及next 數(shù)組分別如下：
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3333.jpg" alt="" />
根據(jù)最大長度表求出了 next 數(shù)組后，從而有
| 失配時(shí)，模式串向右移動(dòng)的位數(shù)為：失配字符所在位置?- 失配字符對(duì)應(yīng)的next 值 |
而后，你會(huì)發(fā)現(xiàn)，無論是基于《最大長度表》的匹配，還是基于 next 數(shù)組的匹配，兩者得出來的向右移動(dòng)的位數(shù)是一樣的。為什么呢？因?yàn)椋?/p>
所以，你可以把《最大長度表》看做是 next 數(shù)組的雛形，甚至就把它當(dāng)做 next 數(shù)組也是可以的，區(qū)別不過是怎么用的問題。
基于之前的理解，可知計(jì)算 next 數(shù)組的方法可以采用遞推：
舉個(gè)例子，如下圖，根據(jù)模式串“ABCDABD”的 next 數(shù)組可知失配位置的字符 D 對(duì)應(yīng)的 next 值為 2，代表字符 D 前有長度為 2 的相同前綴和后綴（這個(gè)相同的前綴后綴即為“AB”），失配后，模式串需要向右移動(dòng) j - next [j] = 6 - 2 =4 位。
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3341.png" alt="" />
向右移動(dòng) 4 位后，模式串中的字符 C 繼續(xù)跟文本串匹配。
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3342.png" alt="" />
對(duì)于 P 的前 j+1 個(gè)序列字符：
一般的文章或教材可能就此一筆帶過，但大部分的初學(xué)者可能還是不能很好的理解上述求解 next 數(shù)組的原理，故接下來，我再來著重說明下。
如下圖所示，假定給定模式串 ABCDABCE，且已知 next [j] = k（相當(dāng)于“p0 pk-1” = “pj-k pj-1” = AB，可以看出 k 為 2），現(xiàn)要求 next [j + 1] 等于多少？因?yàn)?pk = pj = C，所以 next[j + 1] = next[j] + 1 = k + 1（可以看出 next[j + 1] = 3）。代表字符 E 前的模式串中，有長度 k+1 的相同前綴后綴。
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3343.jpg" alt="" />
但如果 pk != pj 呢？說明“p0 pk-1 pk” ≠ “pj-k pj-1 pj”。換言之，當(dāng) pk != pj 后，字符 E 前有多大長度的相同前綴后綴呢？很明顯，因?yàn)?C 不同于 D，所以 ABC 跟 ABD 不相同，即字符 E 前的模式串沒有長度為 k+1 的相同前綴后綴，也就不能再簡單的令：next[j + 1] = next[j] + 1 。所以，咱們只能去尋找長度更短一點(diǎn)的相同前綴后綴。
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3344.jpg" alt="" />
結(jié)合上圖來講，若能在前綴“ p0 pk-1 pk ” 中不斷的遞歸前綴索引 k = next [k]，找到一個(gè)字符 pk’ 也為 D，代表 pk’ = pj，且滿足 p0 pk'-1 pk' = pj-k' pj-1 pj，則最大相同的前綴后綴長度為 k' + 1，從而 next [j + 1] = k’ + 1 = next [k' ] + 1。否則前綴中沒有 D，則代表沒有相同的前綴后綴，next [j + 1] = 0。
那為何遞歸前綴索引k = next[k]，就能找到長度更短的相同前綴后綴呢？這又歸根到 next 數(shù)組的含義。我們拿前綴 p0 pk-1 pk 去跟后綴 pj-k pj-1 pj 匹配，如果 pk 跟 pj 失配，下一步就是用 p[next[k]] 去跟 pj 繼續(xù)匹配，如果 p[ next[k] ]跟 pj 還是不匹配，則需要尋找長度更短的相同前綴后綴，即下一步用 p[ next[ next[k] ] ] 去跟 pj 匹配。此過程相當(dāng)于模式串的自我匹配，所以不斷的遞歸 k = next[k]，直到要么找到長度更短的相同前綴后綴，要么沒有長度更短的相同前綴后綴。如下圖所示：
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3345.png" alt="" />
所以，因最終在前綴 ABC 中沒有找到 D，故 E 的 next 值為 0：
模式串的后綴：ABDE
模式串的前綴：ABC
前綴右移兩位： ABC
讀到此，有的讀者可能又有疑問了，那能否舉一個(gè)能在前綴中找到字符 D 的例子呢？OK，咱們便來看一個(gè)能在前綴中找到字符 D 的例子，如下圖所示：
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3346.jpg" alt="" />
給定模式串 DABCDABDE，我們很順利的求得字符 D 之前的“DABCDAB”的各個(gè)子串的最長相同前綴后綴的長度分別為 0 0 0 0 1 2 3，但當(dāng)遍歷到字符 D，要求包括 D 在內(nèi)的“DABCDABD”最長相同前綴后綴時(shí)，我們發(fā)現(xiàn) pj 處的字符 D 跟 pk 處的字符 C 不一樣，換言之，前綴 DABC 的最后一個(gè)字符 C 跟后綴 DABD 的最后一個(gè)字符 D 不相同，所以不存在長度為 4 的相同前綴后綴。
怎么辦呢？既然沒有長度為 4 的相同前綴后綴，咱們可以尋找長度短點(diǎn)的相同前綴后綴，最終，因在 p0 處發(fā)現(xiàn)也有個(gè)字符 D，p0 = pj，所以 p[j] 對(duì)應(yīng)的長度值為 1，相當(dāng)于 E 對(duì)應(yīng)的 next 值為 1（即字符 E 之前的字符串“DABCDABD”中有長度為 1 的相同前綴和后綴）。
綜上，可以通過遞推求得 next 數(shù)組，代碼如下所示：
void GetNext(char* p,int next[])
{
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{
//p[k]表示前綴，p[j]表示后綴
if (k == -1 || p[j] == p[k])
{
++k;
++j;
next[j] = k;
}
else
{
k = next[k];
}
}
} 用代碼重新計(jì)算下“ABCDABD”的 next 數(shù)組，以驗(yàn)證之前通過“最長相同前綴后綴長度值右移一位，然后初值賦為 -1” 得到的 next 數(shù)組是否正確，計(jì)算結(jié)果如下表格所示：
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3347.jpg" alt="" />
從上述表格可以看出，無論是之前通過“最長相同前綴后綴長度值右移一位，然后初值賦為 -1” 得到的 next 數(shù)組，還是之后通過代碼遞推計(jì)算求得的 next 數(shù)組，結(jié)果是完全一致的。
下面，我們來基于 next 數(shù)組進(jìn)行匹配。
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3351.jpg" alt="" />
還是給定文本串“BBC ABCDAB ABCDABCDABDE”，和模式串“ABCDABD”，現(xiàn)在要拿模式串去跟文本串匹配，如下圖所示：
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3352.png" alt="" />
在正式匹配之前，讓我們來再次回顧下上文 2.1 節(jié)所述的 KMP 算法的匹配流程：
“假設(shè)現(xiàn)在文本串S匹配到 i 位置，模式串 P 匹配到 j 位置
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3353.png" alt="" />
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3354.png" alt="" />
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3355.png" alt="" />
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3356.png" alt="" />
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3357.png" alt="" />
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3358.png" alt="" />
匹配過程一模一樣。也從側(cè)面佐證了，next 數(shù)組確實(shí)是只要將各個(gè)最大前綴后綴的公共元素的長度值右移一位，且把初值賦為 -1 即可。
我們已經(jīng)知道，利用 next 數(shù)組進(jìn)行匹配失配時(shí)，模式串向右移動(dòng) j - next [ j ] 位，等價(jià)于已匹配字符數(shù) - 失配字符的上一位字符所對(duì)應(yīng)的最大長度值。原因是：
但為何本文不直接利用 next 數(shù)組進(jìn)行匹配呢？因?yàn)?next 數(shù)組不好求，而一個(gè)字符串的前綴后綴的公共元素的最大長度值很容易求。例如若給定模式串“ababa”，要你快速口算出其 next 數(shù)組，乍一看，每次求對(duì)應(yīng)字符的 next 值時(shí)，還得把該字符排除之外，然后看該字符之前的字符串中有最大長度為多大的相同前綴后綴，此過程不夠直接。而如果讓你求其前綴后綴公共元素的最大長度，則很容易直接得出結(jié)果：0 0 1 2 3，如下表格所示：
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3361.jpg" alt="" />
然后這 5 個(gè)數(shù)字 全部整體右移一位，且初值賦為 -1，即得到其 next 數(shù)組：-1 0 0 1 2。
next 負(fù)責(zé)把模式串向前移動(dòng)，且當(dāng)?shù)趈位不匹配的時(shí)候，用第 next[j] 位和主串匹配，就像打了張“表”。此外，next 也可以看作有限狀態(tài)自動(dòng)機(jī)的狀態(tài)，在已經(jīng)讀了多少字符的情況下，失配后，前面讀的若干個(gè)字符是有用的。
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3371.png" alt="" />
行文至此，咱們?nèi)媪私饬吮┝ζヅ涞乃悸?、KMP算法的原理、流程、流程之間的內(nèi)在邏輯聯(lián)系，以及 next 數(shù)組的簡單求解（《最大長度表》整體右移一位，然后初值賦為 -1）和代碼求解，最后基于《next 數(shù)組》的匹配，看似洋洋灑灑，清晰透徹，但以上忽略了一個(gè)小問題。
比如，如果用之前的 next 數(shù)組方法求模式串“abab”的 next 數(shù)組，可得其 next 數(shù)組為-1 0 0 1（0 0 1 2整體右移一位，初值賦為 -1），當(dāng)它跟下圖中的文本串去匹配的時(shí)候，發(fā)現(xiàn) b 跟 c 失配，于是模式串右移 j - next[j] = 3 - 1 =2 位。
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3381.jpg" alt="" />
右移 2 位后，b 又跟 c 失配。事實(shí)上，因?yàn)樵谏弦徊降钠ヅ渲?，已?jīng)得知 p[3] = b，與 s[3] = c 失配，而右移兩位之后，讓 p[ next[3] ] = p[1] = b 再跟 s[3] 匹配時(shí)，必然失配。問題出在哪呢？
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3382.jpg" alt="" />
問題出在不該出現(xiàn) p[j] = p[ next[j] ]。為什么呢？理由是：當(dāng) p[j] != s[i] 時(shí)，下次匹配必然是 p[ next [j]] 跟 s[i] 匹配，如果 p[j] = p[ next[j] ]，必然導(dǎo)致后一步匹配失敗（因?yàn)?p[j] 已經(jīng)跟 s[i] 失配，然后你還用跟 p[j] 等同的值 p[next[j]] 去跟 s[i] 匹配，很顯然，必然失配），所以不能允許 p[j] = p[ next[j ]]。如果出現(xiàn)了 p[j] = p[ next[j] ] 咋辦呢？如果出現(xiàn)了，則需要再次遞歸，即令 next[j] = next[ next[j] ]。
所以，咱們得修改下求 next 數(shù)組的代碼。
//優(yōu)化過后的next 數(shù)組求法
void GetNextval(char* p, int next[])
{
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{
//p[k]表示前綴，p[j]表示后綴
if (k == -1 || p[j] == p[k])
{
++j;
++k;
//較之前next數(shù)組求法，改動(dòng)在下面4行
if (p[j] != p[k])
next[j] = k; //之前只有這一行
else
//因?yàn)椴荒艹霈F(xiàn)p[j] = p[ next[j ]]，所以當(dāng)出現(xiàn)時(shí)需要繼續(xù)遞歸，k = next[k] = next[next[k]]
next[j] = next[k];
}
else
{
k = next[k];
}
}
} 利用優(yōu)化過后的 next 數(shù)組求法，可知模式串“abab”的新 next 數(shù)組為：-1 0 -1 0?？赡苡行┳x者會(huì)問：原始next 數(shù)組是前綴后綴最長公共元素長度值右移一位， 然后初值賦為 -1 而得，那么優(yōu)化后的 next 數(shù)組如何快速心算出呢？實(shí)際上，只要求出了原始 next 數(shù)組，便可以根據(jù)原始 next 數(shù)組快速求出優(yōu)化后的 next 數(shù)組。還是以 abab 為例，如下表格所示：
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3383.jpg" alt="" />
只要出現(xiàn)了 p[next[j]] = p[j] 的情況，則把 next[j] 的值再次遞歸。例如在求模式串“abab”的第 2 個(gè) a 的 next 值時(shí)，如果是未優(yōu)化的 next 值的話，第 2 個(gè) a 對(duì)應(yīng)的 next 值為 0，相當(dāng)于第 2 個(gè) a 失配時(shí)，下一步匹配模式串會(huì)用 p[0] 處的 a 再次跟文本串匹配，必然失配。所以求第 2 個(gè) a 的 next 值時(shí)，需要再次遞歸：next[2] = next[ next[2] ] = next[0] = -1（此后，根據(jù)優(yōu)化后的新 next 值可知，第 2 個(gè) a 失配時(shí)，執(zhí)行“如果 j = -1，或者當(dāng)前字符匹配成功（即 S[i] == P[j]），都令 i++，j++，繼續(xù)匹配下一個(gè)字符”），同理，第 2 個(gè) b 對(duì)應(yīng)的 next 值為 0。
對(duì)于優(yōu)化后的 next 數(shù)組可以發(fā)現(xiàn)一點(diǎn)：如果模式串的后綴跟前綴相同，那么它們的 next 值也是相同的，例如模式串 abcabc，它的前綴后綴都是 abc，其優(yōu)化后的 next 數(shù)組為：-1 0 0 -1 0 0，前綴后綴 abc 的 next 值都為 -1 0 0。
然后引用下之前 3.1 節(jié)的 KMP 代碼：
int KmpSearch(char* s, char* p)
{
int i = 0;
int j = 0;
int sLen = strlen(s);
int pLen = strlen(p);
while (i < sLen && j < pLen)
{
//①如果j = -1，或者當(dāng)前字符匹配成功（即S[i] == P[j]），都令i++，j++
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
//②如果j != -1，且當(dāng)前字符匹配失?。碨[i] != P[j]），則令 i 不變，j = next[j]
//next[j]即為j所對(duì)應(yīng)的next值
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
} 接下來，咱們繼續(xù)拿之前的例子說明，整個(gè)匹配過程如下：
1.S[3] 與 P[3] 匹配失敗。
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3385.jpg" alt="" />
2.S[3] 保持不變，P 的下一個(gè)匹配位置是 P[next[3]]，而 next[3]=0，所以 P[next[3]]=P[0] 與 S[3] 匹配。
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3386.jpg" alt="" />
3.由于上一步驟中 P[0] 與 S[3] 還是不匹配。此時(shí) i=3，j=next [0]=-1，由于滿足條件 j==-1，所以執(zhí)行“++i, ++j”，即主串指針下移一個(gè)位置，P[0] 與 S[4] 開始匹配。最后 j==pLen，跳出循環(huán)，輸出結(jié)果 i - j = 4（即模式串第一次在文本串中出現(xiàn)的位置），匹配成功，算法結(jié)束。
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3387.jpg" alt="" />
相信大部分讀者讀完上文之后，已經(jīng)發(fā)覺其實(shí)理解 KMP 非常容易，無非是循序漸進(jìn)把握好下面幾點(diǎn)：
如之前的圖所示：
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/341.jpg" alt="" />
接下來，咱們來分析下 KMP 的時(shí)間復(fù)雜度。分析之前，先來回顧下 KMP 匹配算法的流程：
“KMP 的算法流程：
我們發(fā)現(xiàn)如果某個(gè)字符匹配成功，模式串首字符的位置保持不動(dòng)，僅僅是 i++、j++；如果匹配失配，i 不變（即 i 不回溯），模式串會(huì)跳過匹配過的 next [j] 個(gè)字符。整個(gè)算法最壞的情況是，當(dāng)模式串首字符位于 i - j 的位置時(shí)才匹配成功，算法結(jié)束。
所以，如果文本串的長度為 n，模式串的長度為 m，那么匹配過程的時(shí)間復(fù)雜度為 O(n)，算上計(jì)算 next 的 O(m) 時(shí)間，KMP 的整體時(shí)間復(fù)雜度為 O(m + n)。
掃碼關(guān)注鍍金池微信號(hào)
手機(jī)訂課，優(yōu)惠多多