3. KMP 算法

3.1 定義

Knuth-Morris-Pratt 字符串查找算法，簡稱為 “KMP 算法”，常用于在一個文本串 S 內(nèi)查找一個模式串 P 的出現(xiàn)位置，這個算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年聯(lián)合發(fā)表，故取這三人的姓氏命名此算法。

下面先直接給出 KMP 的算法流程（如果感到一點點不適，沒關(guān)系，堅持下，稍后會有具體步驟及解釋，越往后看越會柳暗花明 ?）：

• 假設(shè)現(xiàn)在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置
  • 如果 j = -1，或者當前字符匹配成功（即 S[i] == P[j]），都令 i++，j++，繼續(xù)匹配下一個字符；
  • 如果 j != -1，且當前字符匹配失?。?S[i] != P[j]），則令 i 不變，j = next[j]。此舉意味著失配時，模式串 P 相對于文本串 S 向右移動了 j - next [j] 位。
    • 換言之，當匹配失敗時，模式串向右移動的位數(shù)為：失配字符所在位置 - 失配字符對應(yīng)的 next 值（next 數(shù)組的求解會在下文的 3.3.3 節(jié)中詳細闡述），即移動的實際位數(shù)為：j - next[j]，且此值大于等于1。

很快，你也會意識到 next 數(shù)組各值的含義：代表當前字符之前的字符串中，有多大長度的相同前綴后綴。例如，如果 next [j] = k，代表 j 之前的字符串中有最大長度為 k 的相同前綴后綴。

此也意味著在某個字符失配時，該字符對應(yīng)的 next 值會告訴你下一步匹配中，模式串應(yīng)該跳到哪個位置（跳到next [j] 的位置）。如果 next [j] 等于 0 或 -1，則跳到模式串的開頭字符，若 next [j] = k 且 k > 0，代表下次匹配跳到 j 之前的某個字符，而不是跳到開頭，且具體跳過了 k 個字符。

轉(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，或者當前字符匹配成功（即S[i] == P[j]），都令i++，j++      
        if (j == -1 || s[i] == p[j])  
        {  
            i++;  
            j++;  
        }  
        else  
        {  
            //②如果j != -1，且當前字符匹配失?。碨[i] != P[j]），則令 i 不變，j = next[j]      
            //next[j]即為j所對應(yīng)的next值        
            j = next[j];  
        }  
    }  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  
}  

繼續(xù)拿之前的例子來說，當 S[10] 跟 P[6] 匹配失敗時，KMP 不是跟暴力匹配那樣簡單的把模式串右移一位，而是執(zhí)行第 ② 條指令：“如果 j != -1，且當前字符匹配失敗（即 S[i] != P[j]），則令 i 不變，j = next[j]”，即 j 從 6 變到 2（后面我們將求得 P[6]，即字符 D 對應(yīng)的 next 值為 2），所以相當于模式串向右移動的位數(shù)為 j - next[j]（j - next[j] = 6-2 = 4）。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3-1.png" alt="" />

向右移動 4 位后，S[10] 跟 P[2] 繼續(xù)匹配。為什么要向右移動 4 位呢，因為移動 4 位后，模式串中又有個“AB”可以繼續(xù)跟 S[8]S[9] 對應(yīng)著，從而不用讓 i 回溯。相當于在除去字符 D 的模式串子串中尋找相同的前綴和后綴，然后根據(jù)前綴后綴求出next 數(shù)組，最后基于 next 數(shù)組進行匹配（不關(guān)心 next 數(shù)組是怎么求來的，只想看匹配過程是咋樣的，可直接跳到下文 3.3.4 節(jié)）。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3-2.png" alt="" />

3.2 步驟

• ① 尋找前綴后綴最長公共元素長度

對于 P = p0 p1 ...pj-1 pj，尋找模式串 P 中長度最大且相等的前綴和后綴。如果存在 p0 p1 ...pk-1 pk = pj- k pj-k+1...pj-1 pj，那么在包含 pj 的模式串中有最大長度為 k+1 的相同前綴后綴。舉個例子，如果給定的模式串為“abab”，那么它的各個子串的前綴后綴的公共元素的最大長度如下表格所示：

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/321.jpg" alt="" />

比如對于字符串 aba 來說，它有長度為 1 的相同前綴后綴 a；而對于字符串 abab 來說，它有長度為 2 的相同前綴后綴ab（相同前綴后綴的長度為 k + 1，k + 1 = 2）。

• ② 求 next 數(shù)組

next 數(shù)組考慮的是除當前字符外的最長相同前綴后綴，所以通過第 ① 步驟求得各個前綴后綴的公共元素的最大長度后，只要稍作變形即可：將第 ① 步驟中求得的值整體右移一位，然后初值賦為 -1，如下表格所示：

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/322.jpg" alt="" />

比如對于 aba 來說，第 3 個字符 a 之前的字符串 ab 中有長度為 0 的相同前綴后綴，所以第 3 個字符 a 對應(yīng)的 next 值為 0；而對于 abab 來說，第 4 個字符 b 之前的字符串 aba 中有長度為 1 的相同前綴后綴 a，所以第 4 個字符 b 對應(yīng)的 next 值為 1（相同前綴后綴的長度為 k，k = 1）。

• ③ 根據(jù) next 數(shù)組進行匹配

匹配失配，j = next [j]，模式串向右移動的位數(shù)為：j - next[j]。換言之，當模式串的后綴 pj-k pj-k+1, ..., pj-1 跟文本串 si-k si-k+1, ..., si-1 匹配成功，但 pj 跟 si 匹配失敗時，因為 next[j] = k，相當于在不包含 pj 的模式串中有最大長度為 k 的相同前綴后綴，即 p0 p1 ...pk-1 = pj-k pj-k+1...pj-1，故令 j = next[j]，從而讓模式串右移 j - next[j] 位，使得模式串的前綴 p0 p1, ..., pk-1 對應(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ù)組相當于告訴我們：當模式串中的某個字符跟文本串中的某個字符匹配失配時，模式串下一步應(yīng)該跳到哪個位置。如模式串中在j 處的字符跟文本串在 i 處的字符匹配失配時，下一步用 next [j] 處的字符繼續(xù)跟文本串 i 處的字符匹配，相當于模式串向右移動 j - next[j] 位。

接下來，分別具體解釋上述 3 個步驟。

3.3 解釋

3.3.1 尋找最長前綴后綴

如果給定的模式串是：“ABCDABD”，從左至右遍歷整個模式串，其各個子串的前綴后綴分別如下表格所示：

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/331.jpg" alt="" />

也就是說，原模式串子串對應(yīng)的各個前綴后綴的公共元素的最大長度表為（下簡稱《最大長度表》）：

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3311.jpg" alt="" />

3.3.2 基于《最大長度表》匹配

因為模式串中首尾可能會有重復(fù)的字符，故可得出下述結(jié)論：

下面，咱們就結(jié)合之前的《最大長度表》和上述結(jié)論，進行字符串的匹配。如果給定文本串“BBC ABCDAB ABCDABCDABDE”，和模式串“ABCDABD”，現(xiàn)在要拿模式串去跟文本串匹配，如下圖所示：

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3320.png" alt="" />

• 1.因為模式串中的字符 A 跟文本串中的字符 B、B、C、空格一開始就不匹配，所以不必考慮結(jié)論，直接將模式串不斷的右移一位即可，直到模式串中的字符 A 跟文本串的第 5 個字符 A 匹配成功：

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3321.png" alt="" />

• 2.繼續(xù)往后匹配，當模式串最后一個字符 D 跟文本串匹配時失配，顯而易見，模式串需要向右移動。但向右移動多少位呢？因為此時已經(jīng)匹配的字符數(shù)為 6 個（ABCDAB），然后根據(jù)《最大長度表》可得失配字符 D 的上一位字符B對應(yīng)的長度值為 2，所以根據(jù)之前的結(jié)論，可知需要向右移動 6 - 2 = 4 位。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3322.png" alt="" />

• 3.模式串向右移動 4 位后，發(fā)現(xiàn) C 處再度失配，因為此時已經(jīng)匹配了 2 個字符（AB），且上一位字符 B 對應(yīng)的最大長度值為 0，所以向右移動：2 - 0 =2 位。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3323.png" alt="" />

• 4.A 與空格失配，向右移動 1 位。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3324.png" alt="" />

• 5.繼續(xù)比較，發(fā)現(xiàn) D 與 C 失配，故向右移動的位數(shù)為：已匹配的字符數(shù) 6 減去上一位字符 B 對應(yīng)的最大長度 2，即向右移動 6 - 2 = 4 位。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3325.png" alt="" />

• 6.經(jīng)歷第 5 步后，發(fā)現(xiàn)匹配成功，過程結(jié)束。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3326.png" alt="" />

通過上述匹配過程可以看出，問題的關(guān)鍵就是尋找模式串中最大長度的相同前綴和后綴，找到了模式串中每個字符之前的前綴和后綴公共部分的最大長度后，便可基于此匹配。而這個最大長度便正是 next 數(shù)組要表達的含義。

3.3.3 根據(jù)《最大長度表》求 next 數(shù)組

由上文，我們已經(jīng)知道，字符串“ABCDABD”各個前綴后綴的最大公共元素長度分別為：

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3331.jpg" alt="" />

而且，根據(jù)這個表可以得出下述結(jié)論

• 失配時，模式串向右移動的位數(shù)為：已匹配字符數(shù) - 失配字符的上一位字符所對應(yīng)的最大長度值

上文利用這個表和結(jié)論進行匹配時，我們發(fā)現(xiàn)，當匹配到一個字符失配時，其實沒必要考慮當前失配的字符，更何況我們每次失配時，都是看的失配字符的上一位字符對應(yīng)的最大長度值。如此，便引出了 next 數(shù)組。

給定字符串“ABCDABD”，可求得它的 next 數(shù)組如下：

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3332.jpg" alt="" />

把 next 數(shù)組跟之前求得的最大長度表對比后，不難發(fā)現(xiàn)，next 數(shù)組相當于“最大長度值” 整體向右移動一位，然后初始值賦為 -1。意識到了這一點，你會驚呼原來 next 數(shù)組的求解竟然如此簡單：就是找最大對稱長度的前綴后綴，然后整體右移一位，初值賦為 -1（當然，你也可以直接計算某個字符對應(yīng)的 next 值，就是看這個字符之前的字符串中有多大長度的相同前綴后綴）。

換言之，對于給定的模式串：ABCDABD，它的最大長度表及next 數(shù)組分別如下：

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3333.jpg" alt="" />

根據(jù)最大長度表求出了 next 數(shù)組后，從而有

而后，你會發(fā)現(xiàn)，無論是基于《最大長度表》的匹配，還是基于 next 數(shù)組的匹配，兩者得出來的向右移動的位數(shù)是一樣的。為什么呢？因為：

• 根據(jù)《最大長度表》，失配時，模式串向右移動的位數(shù) = 已經(jīng)匹配的字符數(shù) - 失配字符的上一位字符的最大長度值
• 而根據(jù)《next 數(shù)組》，失配時，模式串向右移動的位數(shù) = 失配字符的位置 - 失配字符對應(yīng)的 next 值
  • 其中，從 0 開始計數(shù)時，失配字符的位置 = 已經(jīng)匹配的字符數(shù)（失配字符不計數(shù)），而失配字符對應(yīng)的 next 值 = 失配字符的上一位字符的最大長度值，兩相比較，結(jié)果必然完全一致。

所以，你可以把《最大長度表》看做是 next 數(shù)組的雛形，甚至就把它當做 next 數(shù)組也是可以的，區(qū)別不過是怎么用的問題。

　3.3.4 通過代碼遞推計算 next 數(shù)組

接下來，咱們來寫代碼求下 next 數(shù)組。

基于之前的理解，可知計算 next 數(shù)組的方法可以采用遞推：

• 1.如果對于值 k，已有 p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，相當于 next[j] = k。 此意味著什么呢？究其本質(zhì)，next[j] = k 代表 p[j] 之前的模式串子串中，有長度為 k 的相同前綴和后綴。有了這個 next 數(shù)組，在 KMP 匹配中，當模式串中 j 處的字符失配時，下一步用 next[j] 處的字符繼續(xù)跟文本串匹配，相當于模式串向右移動 j - next[j] 位。

舉個例子，如下圖，根據(jù)模式串“ABCDABD”的 next 數(shù)組可知失配位置的字符 D 對應(yīng)的 next 值為 2，代表字符 D 前有長度為 2 的相同前綴和后綴（這個相同的前綴后綴即為“AB”），失配后，模式串需要向右移動 j - next [j] = 6 - 2 =4 位。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3341.png" alt="" />

向右移動 4 位后，模式串中的字符 C 繼續(xù)跟文本串匹配。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3342.png" alt="" />

• 2.下面的問題是：已知 next [0, ..., j]，如何求出 next [j + 1] 呢？

對于 P 的前 j+1 個序列字符：

• 若p[k] == p[j]，則 next[j + 1 ] = next [j] + 1 = k + 1；
• 若p[k ] ≠ p[j]，如果此時 p[ next[k] ] == p[j ]，則 next[ j + 1 ] = next[k] + 1，否則繼續(xù)遞歸前綴索引 k = next[k]，而后重復(fù)此過程。 相當于在字符 p[j+1] 之前不存在長度為 k+1 的前綴"p0 p1, …, pk-1 pk"跟后綴“pj-k pj-k+1, …, pj-1 pj"相等，那么是否可能存在另一個值 t+1 < k+1，使得長度更小的前綴 “p0 p1, …, pt-1 pt” 等于長度更小的后綴 “pj-t pj-t+1, …, pj-1 pj” 呢？如果存在，那么這個 t+1 便是 next[ j+1] 的值，此相當于利用已經(jīng)求得的 next 數(shù)組（next [0, ..., k, ..., j]）進行 P 串前綴跟 P 串后綴的匹配。

一般的文章或教材可能就此一筆帶過，但大部分的初學者可能還是不能很好的理解上述求解 next 數(shù)組的原理，故接下來，我再來著重說明下。

如下圖所示，假定給定模式串 ABCDABCE，且已知 next [j] = k（相當于“p0 pk-1” = “pj-k pj-1” = AB，可以看出 k 為 2），現(xiàn)要求 next [j + 1] 等于多少？因為 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”。換言之，當 pk != pj 后，字符 E 前有多大長度的相同前綴后綴呢？很明顯，因為 C 不同于 D，所以 ABC 跟 ABD 不相同，即字符 E 前的模式串沒有長度為 k+1 的相同前綴后綴，也就不能再簡單的令：next[j + 1] = next[j] + 1 。所以，咱們只能去尋找長度更短一點的相同前綴后綴。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3344.jpg" alt="" />

結(jié)合上圖來講，若能在前綴“ p0 pk-1 pk ” 中不斷的遞歸前綴索引 k = next [k]，找到一個字符 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 匹配。此過程相當于模式串的自我匹配，所以不斷的遞歸 k = next[k]，直到要么找到長度更短的相同前綴后綴，要么沒有長度更短的相同前綴后綴。如下圖所示：

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3345.png" alt="" />

所以，因最終在前綴 ABC 中沒有找到 D，故 E 的 next 值為 0：

模式串的后綴：ABDE
模式串的前綴：ABC
前綴右移兩位：    ABC

讀到此，有的讀者可能又有疑問了，那能否舉一個能在前綴中找到字符 D 的例子呢？OK，咱們便來看一個能在前綴中找到字符 D 的例子，如下圖所示：

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3346.jpg" alt="" />

給定模式串 DABCDABDE，我們很順利的求得字符 D 之前的“DABCDAB”的各個子串的最長相同前綴后綴的長度分別為 0 0 0 0 1 2 3，但當遍歷到字符 D，要求包括 D 在內(nèi)的“DABCDABD”最長相同前綴后綴時，我們發(fā)現(xiàn) pj 處的字符 D 跟 pk 處的字符 C 不一樣，換言之，前綴 DABC 的最后一個字符 C 跟后綴 DABD 的最后一個字符 D 不相同，所以不存在長度為 4 的相同前綴后綴。

怎么辦呢？既然沒有長度為 4 的相同前綴后綴，咱們可以尋找長度短點的相同前綴后綴，最終，因在 p0 處發(fā)現(xiàn)也有個字符 D，p0 = pj，所以 p[j] 對應(yīng)的長度值為 1，相當于 E 對應(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];  
        }  
    }  
}  

用代碼重新計算下“ABCDABD”的 next 數(shù)組，以驗證之前通過“最長相同前綴后綴長度值右移一位，然后初值賦為 -1” 得到的 next 數(shù)組是否正確，計算結(jié)果如下表格所示：

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3347.jpg" alt="" />

從上述表格可以看出，無論是之前通過“最長相同前綴后綴長度值右移一位，然后初值賦為 -1” 得到的 next 數(shù)組，還是之后通過代碼遞推計算求得的 next 數(shù)組，結(jié)果是完全一致的。

3.3.5 基于《next 數(shù)組》匹配

下面，我們來基于 next 數(shù)組進行匹配。

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 位置

  • 如果 j = -1，或者當前字符匹配成功（即 S[i] == P[j]），都令 i++，j++，繼續(xù)匹配下一個字符；
  • 如果 j != -1，且當前字符匹配失?。?S[i] != P[j]），則令 i 不變，j = next[j]。此舉意味著失配時，模式串 P 相對于文本串 S 向右移動了 j - next [j] 位。
    • 換言之，當匹配失敗時，模式串向右移動的位數(shù)為：失配字符所在位置 - 失配字符對應(yīng)的 next 值，即移動的實際位數(shù)為：j - next[j]，且此值大于等于1?！?/li>
• 1.最開始匹配時
  • P[0] 跟 S[0] 匹配失敗
    • 所以執(zhí)行“如果 j != -1，且當前字符匹配失?。?S[i] != P[j]），則令 i 不變，j = next[j]”，所以 j = -1，故轉(zhuǎn)而執(zhí)行“如果 j = -1，或者當前字符匹配成功（即 S[i] == P[j]），都令 i++，j++”，得到i = 1，j = 0，即 P[0] 繼續(xù)跟 S[1] 匹配。
  • P[0] 跟 S[1] 又失配，j 再次等于 -1，i、j 繼續(xù)自增，從而 P[0] 跟 S[2] 匹配。
  • P[0] 跟 S[2] 失配后，P[0] 又跟 S[3] 匹配。
  • P[0] 跟 S[3] 再失配，直到 P[0] 跟 S[4] 匹配成功，開始執(zhí)行此條指令的后半段：“如果 j = -1，或者當前字符匹配成功（即 S[i] == P[j]），都令 i++，j++”。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3353.png" alt="" />

• 2.P[1] 跟 S[5] 匹配成功，P[2] 跟 S[6] 也匹配成功, ...，直到當匹配到 P[6] 處的字符 D 時失配（即 S[10] != P[6]），由于 P[6] 處的 D 對應(yīng)的 next 值為 2，所以下一步用 P[2] 處的字符 C 繼續(xù)跟 S[10] 匹配，相當于向右移動：j - next[j] = 6 - 2 =4 位。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3354.png" alt="" />

• 3.向右移動 4 位后，P[2] 處的 C 再次失配，由于 C 對應(yīng)的 next 值為 0，所以下一步用 P[0] 處的字符繼續(xù)跟 S[10] 匹配，相當于向右移動：j - next[j] = 2 - 0 = 2 位。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3355.png" alt="" />

• 4.移動兩位之后，A 跟空格不匹配，模式串后移 1 位。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3356.png" alt="" />

• 5.P[6] 處的 D 再次失配，因為 P[6] 對應(yīng)的 next 值為 2，故下一步用 P[2] 繼續(xù)跟文本串匹配，相當于模式串向右移動 j - next[j] = 6 - 2 = 4 位。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3357.png" alt="" />

• 6.匹配成功，過程結(jié)束。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3358.png" alt="" />

匹配過程一模一樣。也從側(cè)面佐證了，next 數(shù)組確實是只要將各個最大前綴后綴的公共元素的長度值右移一位，且把初值賦為 -1 即可。

3.3.6 基于《最大長度表》與基于《next 數(shù)組》等價

我們已經(jīng)知道，利用 next 數(shù)組進行匹配失配時，模式串向右移動 j - next [ j ] 位，等價于已匹配字符數(shù) - 失配字符的上一位字符所對應(yīng)的最大長度值。原因是：

• j 從 0 開始計數(shù)，那么當數(shù)到失配字符時，j 的數(shù)值就是已匹配的字符數(shù)；
• 由于 next 數(shù)組是由最大長度值表整體向右移動一位（且初值賦為 -1）得到的，那么失配字符的上一位字符所對應(yīng)的最大長度值，即為當前失配字符的 next 值。

但為何本文不直接利用 next 數(shù)組進行匹配呢？因為 next 數(shù)組不好求，而一個字符串的前綴后綴的公共元素的最大長度值很容易求。例如若給定模式串“ababa”，要你快速口算出其 next 數(shù)組，乍一看，每次求對應(yīng)字符的 next 值時，還得把該字符排除之外，然后看該字符之前的字符串中有最大長度為多大的相同前綴后綴，此過程不夠直接。而如果讓你求其前綴后綴公共元素的最大長度，則很容易直接得出結(jié)果：0 0 1 2 3，如下表格所示：

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3361.jpg" alt="" />

然后這 5 個數(shù)字 全部整體右移一位，且初值賦為 -1，即得到其 next 數(shù)組：-1 0 0 1 2。

3.3.7 Next 數(shù)組與有限狀態(tài)自動機

next 負責把模式串向前移動，且當?shù)趈位不匹配的時候，用第 next[j] 位和主串匹配，就像打了張“表”。此外，next 也可以看作有限狀態(tài)自動機的狀態(tài)，在已經(jīng)讀了多少字符的情況下，失配后，前面讀的若干個字符是有用的。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3371.png" alt="" />

3.3.8 Next 數(shù)組的優(yōu)化

行文至此，咱們?nèi)媪私饬吮┝ζヅ涞乃悸贰MP算法的原理、流程、流程之間的內(nèi)在邏輯聯(lián)系，以及 next 數(shù)組的簡單求解（《最大長度表》整體右移一位，然后初值賦為 -1）和代碼求解，最后基于《next 數(shù)組》的匹配，看似洋洋灑灑，清晰透徹，但以上忽略了一個小問題。

比如，如果用之前的 next 數(shù)組方法求模式串“abab”的 next 數(shù)組，可得其 next 數(shù)組為-1 0 0 1（0 0 1 2整體右移一位，初值賦為 -1），當它跟下圖中的文本串去匹配的時候，發(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 失配。事實上，因為在上一步的匹配中，已經(jīng)得知 p[3] = b，與 s[3] = c 失配，而右移兩位之后，讓 p[ next[3] ] = p[1] = b 再跟 s[3] 匹配時，必然失配。問題出在哪呢？

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3382.jpg" alt="" />

問題出在不該出現(xiàn) p[j] = p[ next[j] ]。為什么呢？理由是：當 p[j] != s[i] 時，下次匹配必然是 p[ next [j]] 跟 s[i] 匹配，如果 p[j] = p[ next[j] ]，必然導致后一步匹配失?。ㄒ驗?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ù)組求法，改動在下面4行  
            if (p[j] != p[k])  
                next[j] = k;   //之前只有這一行  
            else  
                //因為不能出現(xiàn)p[j] = p[ next[j ]]，所以當出現(xiàn)時需要繼續(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。可能有些讀者會問：原始next 數(shù)組是前綴后綴最長公共元素長度值右移一位， 然后初值賦為 -1 而得，那么優(yōu)化后的 next 數(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 個 a 的 next 值時，如果是未優(yōu)化的 next 值的話，第 2 個 a 對應(yīng)的 next 值為 0，相當于第 2 個 a 失配時，下一步匹配模式串會用 p[0] 處的 a 再次跟文本串匹配，必然失配。所以求第 2 個 a 的 next 值時，需要再次遞歸：next[2] = next[ next[2] ] = next[0] = -1（此后，根據(jù)優(yōu)化后的新 next 值可知，第 2 個 a 失配時，執(zhí)行“如果 j = -1，或者當前字符匹配成功（即 S[i] == P[j]），都令 i++，j++，繼續(xù)匹配下一個字符”），同理，第 2 個 b 對應(yīng)的 next 值為 0。

對于優(yōu)化后的 next 數(shù)組可以發(fā)現(xià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，或者當前字符匹配成功（即S[i] == P[j]），都令i++，j++      
        if (j == -1 || s[i] == p[j])  
        {  
            i++;  
            j++;  
        }  
        else  
        {  
            //②如果j != -1，且當前字符匹配失?。碨[i] != P[j]），則令 i 不變，j = next[j]      
            //next[j]即為j所對應(yīng)的next值        
            j = next[j];  
        }  
    }  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  
}  

接下來，咱們繼續(xù)拿之前的例子說明，整個匹配過程如下：

1.S[3] 與 P[3] 匹配失敗。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3385.jpg" alt="" />

2.S[3] 保持不變，P 的下一個匹配位置是 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] 還是不匹配。此時 i=3，j=next [0]=-1，由于滿足條件 j==-1，所以執(zhí)行“++i, ++j”，即主串指針下移一個位置，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="" />

3.4 KMP 的時間復(fù)雜度分析

相信大部分讀者讀完上文之后，已經(jīng)發(fā)覺其實理解 KMP 非常容易，無非是循序漸進把握好下面幾點：

• 如果模式串中存在相同前綴和后綴，即 pj-k pj-k+1, ..., pj-1 = p0 p1, ..., pk-1，那么在 pj 跟 si 失配后，讓模式串的前綴 p0 p1...pk-1 對應(yīng)著文本串 si-k si-k+1...si-1，而后讓 pk 跟 si 繼續(xù)匹配。
• 之前本應(yīng)是 pj 跟 si 匹配，結(jié)果失配了，失配后，令 pk 跟 si 匹配，相當于 j 變成了 k，模式串向右移動 j - k 位。
• 因為 k 的值是可變的，所以我們用 next[j] 表示j處字符失配后，下一次匹配模式串應(yīng)該跳到的位置。換言之，失配前是 j，pj 跟 si 失配時，用 p[ next[j] ]繼續(xù)跟 si 匹配，相當于 j 變成了 next[j]，所以，j = next[j]，等價于把模式串向右移動 j - next [j] 位。
• 而 next[j] 應(yīng)該等于多少呢？ next[j] 的值由 j 之前的模式串子串中有多大長度的相同前綴后綴所決定，如果 j 之前的模式串子串中（不含 j）有最大長度為k的相同前綴后綴，那么 next [j] = k。

如之前的圖所示：

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/341.jpg" alt="" />

接下來，咱們來分析下 KMP 的時間復(fù)雜度。分析之前，先來回顧下 KMP 匹配算法的流程：

“KMP 的算法流程：

• 假設(shè)現(xiàn)在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置
  • 如果 j = -1，或者當前字符匹配成功（即 S[i] == P[j]），都令 i++，j++，繼續(xù)匹配下一個字符；
  • 如果 j != -1，且當前字符匹配失敗（即 S[i] != P[j]），則令 i 不變，j = next[j]。此舉意味著失配時，模式串 P 相對于文本串 S 向右移動了 j - next [j] 位?！?/li>

我們發(fā)現(xiàn)如果某個字符匹配成功，模式串首字符的位置保持不動，僅僅是 i++、j++；如果匹配失配，i 不變（即 i 不回溯），模式串會跳過匹配過的 next [j] 個字符。整個算法最壞的情況是，當模式串首字符位于 i - j 的位置時才匹配成功，算法結(jié)束。

所以，如果文本串的長度為 n，模式串的長度為 m，那么匹配過程的時間復(fù)雜度為 O(n)，算上計算 next 的 O(m) 時間，KMP 的整體時間復(fù)雜度為 O(m + n)。