【KMP算法詳解——适合初學KMP算法的朋友】

相信很多人（包括自己）初識KMP算法的時候始終是丈二和尚摸不着頭腦，要麼完全不知所雲，要麼看不懂書上的解釋，要麼自己覺得好像心裡了解KMP算法的意思，卻說不出個究竟，所謂知其然不知其是以然是也。

     經過七八個小時地仔細研究，終于感覺自己能說出其是以然了，又覺得資料結構書上寫得過于簡潔，不易于初學者接受，于是決定把自己的了解拿出來與大家分享，希望能抛磚引玉，這便是Bill寫這篇文章想要得到的最好結果了

-----------------------------------謹以此文，獻給剛接觸KMP算法的朋友，定有不足之處，望大家指正----------------------------------------

【KMP算法簡介】

         KMP算法是一種改進後的字元串比對算法，由D.E.Knuth與V.R.Pratt和J.H.Morris同時發現，是以人們稱它為克努特——莫裡斯——普拉特操作（簡稱KMP算法）。通過一個輔助函數實作跳過掃描不必要的目标串字元，以達到優化效果。

【傳統字元串比對算法的缺憾】

         Bill認為，對于一種優化的算法，既要知道優化的細節，也更應該了解它的前身（至于KMP是否基于傳統算法，我不清楚，這裡隻作語境上的前身），了解是什麼原因導緻了人們要去優化它，是以加入了這一段：

請看以下傳統字元串比對的代碼：

C++ code

void NativeStrMatching( ElemType Target[], ElemType Pattern[] )            

{            

        register int TarLen = 0;        // Length of Target            

        register int PatLen = 0;        // Length of Pattern            

        // Compute the length of Pattern            

        while( '\0' != Pattern[PatLen] )            

                PatLen++;            

        while( '\0' != Target[TarLen] )            

        {            

                int TmpTarLen = TarLen;            

                for(int i=0; i<PatLen; i++)            

                {            

                        if( Target[TmpTarLen++] != Pattern[i] )            

                                break;            

                        if( i == PatLen-1 )            

                                cout<<"Native String Matching,pattern occurs with shift "<<TarLen<<endl;            

                }            

                TarLen++;            

        }            

}    

【代碼思想】

     傳統比對思想是，從目标串Target的第一個字元開始掃描，逐一與模式串的對應字元進行比對，若該組字元比對，則檢測下一組字元，如遇失配，則退回到Target的第二個字元，重複上述步驟，直到整個Pattern在Target中找到比對，或者已經掃描完整個目标串也沒能夠完成比對為止。

     這樣的算法了解起來很簡單，實作起來也容易，但是其中包含了過多不必要的操作，也就是在目标串中，有些字元是可以直接跳過，不必檢測的。

不妨假設我們的目标串

Target =  "a b c d e a b c d e a b c d f"

需要比對的模式串

Pattern = "c d f";

那麼當比對到如下情況時

由于 'e' != 'f' ，是以失配，那麼下次比對起始位置就是目标串的'd'字元

我們發現這裡照樣失配，直到運作到下述情況

也就是說，中間的四個字元 d e a b 完全沒有必要檢測，直接跳轉到下一個'c'開始的地方進行檢測  

     由此可見傳統算法雖然簡單易行，但其中包含了過多的不必要操作，并不能很好地達到實際工作中需要的效率，是以個人認為此方法适合為初識字元串比對做一個鋪墊作用，有抛磚引玉之意。

     說其抛磚引玉并不為過，對KMP算法的了解便可以基于傳統模式串比對算法進行思考。

【KMP算法的引入】

     既然知道了傳統算法的不足之處，就要對症下藥，優化這個備援的檢測算法。

     KMP算法就能很好地解決這個備援問題。

     其主要思想為：

          在失配後，并不簡單地從目标串下一個字元開始新一輪的檢測，而是依據在檢測之前得到的有用資訊（稍後詳述），直接跳過不必要的檢測，進而達到一個較高的檢測效率。

     如我們的

        當第一次失配後，并不從紅色标記字元'd'開始檢測，而是通過一些有用資訊，直接跳過後幾個肯定不可能比對的備援字元，而直接讓模式串Pattern從目标串的紅色标記字元'c'開始新一輪的檢測，進而達到了減少循環次數的效果

【KMP算法思想詳述與實作】

        前面提到，KMP算法通過一個“有用資訊”可以知道目标串中下一個字元是否有必要被檢測，這個“有用資訊”就是用所謂的“字首函數（一般資料結構書中的next函數）”來存儲的。

        這個函數能夠反映出現失配情況時，系統應該跳過多少無用字元（也即模式串應該向右滑動多長距離）而進行下一次檢測，在上例中，這個距離為4.

        總的來講，KMP算法有2個難點：

              一是這個字首函數的求法。

              二是在得到字首函數之後，怎麼運用這個函數所反映的有效資訊避免不必要的檢測。

下面分為兩個闆塊分别詳述：

【字首函數的引入及實作】

【字首函數的引入】

        對于字首函數，先要了解字首是什麼：

        簡單地說，如字元串A = "abcde"        B = "ab"

        那麼就稱字元串B為A的字首，記為B ⊏ A(注意那不是"包含于"，Bill把它讀作B字首于A)，說句題外話——"⊏"這個符号很形象嘛，封了口的這面相當于頭，在頭前面的就是字首了。

        同理可知 C = "e","de" 等都是 A 的字尾，以為C ⊐ A（Bill把它讀作C字尾于A）

了解了什麼是前、字尾，就來看看什麼是字首函數：

        在這裡不打算引用過多的理論來說明，直接引入執行個體會比較容易了解，看如下示例：

      (下述字元若帶下标，則對應于圖中畫圈字元)

      這裡模式串 P = “ababaca”,在比對了 q=5 個字元後失配，是以，下一步就是要考慮将P向右移多少位進行新的一輪比對檢測。傳統模式中，直接将P右移1位，也就是将P的首字元'a'去和目标串的'b'字元進行檢測，這明顯是多餘的。通過我們肉眼的觀察，可以很簡單的知道應該将模式串P右移到下圖'a3'處再開始新一輪的檢測，直接跳過肯定不比對的字元'b'，那麼我們“肉眼”觀察的這一結果怎麼把它用語言表示出來呢？

     我們的觀察過程是這樣的：

          P的字首"ab"中'a' != 'b'，又因該字首已經比對了T中對應的"ab"，是以，該字首的字元'a1'肯定不會和T中對應的字串"ab"中的'b'比對，也就是将P向右滑動一個位移是無意義的。

          接下來考察P的字首"aba"，發現該字首自身的字首'a1'與自身字尾'a2'相等，"a1 b a2" 已經比對了T中的"a b a3"，是以有 'a2' == 'a3', 故得到 'a1' == 'a3'......

          利用此思想，可推知在已經比對 q=5 個字元的情況下，将P向右移 當且僅當 2個位移時，才能滿足既沒有備援(如把'a'去和'b'比較)，又不會丢失(如把'a1' 直接與 'a4' 開始比較，則丢失了與'a3'的比較)。

          而字首函數就是這樣一種函數，它決定了q與位移的一一對應關系，通過它就可以間接地求得位移s。

     通過對各種模式串進行上述分析(大家可以自己多寫幾個模式串出來自己分析了解)，發現給定一個比對字元數 q ，則唯一對應一個有效位移，如上述q=5,則對應位移為2.

     這就形成了一一對應關系，而這種唯一的關系就是由字首函數決定的。

     這到底是怎樣的一種關系呢？

     通過對諸多模式串執行個體的研究，我們會找到一個規律（規律的證明及引理詳見《算法導論(第二版)》）。

     上例中，P 已經比對的字元串為"ababa",那麼這個字元串中，滿足既是自身真字尾(即不等于自身的字尾)，又是自身最長字首的字元串為"aba"，我們設這個特殊字串的長度為L，顯然，L = 3. 故我們要求的 s = q - L = 5 - 3 = 2 ，滿足前述分析。

     根據這個規律，即可得到我們要求的有效位移s，等于已經比對的字元數 q 減去長度 L。

     即 s = q - L

     因為這個長度 L 與 q 一一對應，決定于q，是以用一函數來表達這一關系非常恰當，這就是所謂的字首函數了。

     因為已經分析得到該關系為一一對應關系，是以用數組來表示該函數是比較恰當的，以數組的下标表示已經比對的字元數 q，以下标對應的資料存儲 L。

【字首函數的實作】

下面就來分析怎麼用代碼來表達這種關系。

這裡采用《算法導論(第二版)》中的思想求解。

不妨以 PrefixFunc[] 表示這個字首函數，那麼我們将得到以下求字首函數的函數：

由于 0 個比對字元數在計算中沒有意義，是以PrefixFunc下标從1開始，也就是從已經有一個字元(即首字元)比對的情況開始

// Compute Prefix function            

void CptPfFunc( ElemType Pattern[], int PrefixFunc[] )                

{      

        register int iLen = 0;    // Length of Pattern[]            

        while( '\0' != Pattern[iLen] )            

                iLen++;            

        int LOLP = 0;     // Lenth of longest prefix            

        PrefixFunc[1] = 0;            

        for( int NOCM=2; NOCM<iLen+1; NOCM++ )     // NOCM represent the number of characters matched            

                while( LOLP>0 && (Pattern[LOLP] != Pattern[NOCM-1]) )            

                        LOLP = PrefixFunc[LOLP];            

                if( Pattern[LOLP] == Pattern[NOCM-1] )            

                        LOLP++;            

                PrefixFunc[NOCM] = LOLP;            

}            

 對此函數的詳解，不妨以一執行個體帶入(建議大家自己手算一下，算完應該就有感覺了)，易于了解：

 不妨設模式串Pattern = "a  b  c  c  a  b  c  c  a  b  c  a"

      Pattern 數組編号： 0  1  2  3  4  5  6  7  8  9 10 11

NOCM 表示 已經比對的字元數

LOLP 表示 既是自身真字尾又是自身最長字首的字元串長度

以下是計算流程：

PrefixFunc[1] = 0； //隻比對一個字元就失配時，顯然該值為零

LOLP = 0；   NOCM = 2；   LOLP = 0;    PrefixFunc[2] = 0;

LOLP = 0；   NOCM = 3；   LOLP = 0;    PrefixFunc[3] = 0;

LOLP = 0；   NOCM = 4；   LOLP = 0;    PrefixFunc[4] = 0;

LOLP = 0；   NOCM = 5；   LOLP = 1;    PrefixFunc[5] = 1;

LOLP = 1；   NOCM = 6；   LOLP = 2;    PrefixFunc[6] = 2;

LOLP = 2；   NOCM = 7；   LOLP = 3;    PrefixFunc[7] = 3;

LOLP = 3；   NOCM = 8；   LOLP = 4;    PrefixFunc[8] = 4;

LOLP = 4；   NOCM = 9；   LOLP = 5;    PrefixFunc[9] = 5;

LOLP = 5；   NOCM = 10； LOLP = 6;    PrefixFunc[10] = 6;

LOLP = 6；   NOCM = 11； LOLP = 7;    PrefixFunc[11] = 7;

LOLP = 7；   NOCM = 12；

---------此時滿足條件while( LOLP>0 && (Pattern[LOLP] != Pattern[NOCM-1]) )-------------

while語句中的執行

{

           LOLP = 7;   NOCM = 12;  LOLP = PrefixFunc[7] = 3;

           LOLP = 3;   NOCM = 12;  LOLP = PrefixFunc[3] = 0;

}

LOLP = 0；   NOCM = 12； LOLP = 1;    PrefixFunc[12] = 1;

最後我們的字首函數 PrefixFunc[] = { 0,0,0,0,1,2,3,4,5,6,7,1 }

其間最精妙的要屬失配時的操作

while( LOLP>0 && (Pattern[LOLP] != Pattern[NOCM-1]) )

              LOLP = PrefixFunc[LOLP];

其中 LOLP = PrefixFunc[LOLP];  遞歸調用PrefixFunc函數，直到整個P字串都再無最長字首或者找到一個之前的滿足條件的最長字首。

 【應用字首函數優化傳統比對算法——KMP算法實作】

由以上分析，不難推導KMP算法的實作

void KMPstrMatching( ElemType Target[], ElemType Pattern[] )            

        int PrefixFunc[MAX_SIZE];            

        register int TarLen = 0;            

        register int PatLen = 0;            

        // Compute the length of array Target and Pattern            

        // Compute the prefix function of Pattern            

        CptPfFunc( Pattern, PrefixFunc );            

        int NOCM = 0;     // Number of characters matched            

        for( int i=0; i<TarLen; i++ )            

                while( NOCM>0 && Pattern[NOCM] != Target[i] )            

                        NOCM = PrefixFunc[NOCM];            

                if( Pattern[NOCM] == Target[i] )            

                        NOCM++;            

                if( NOCM == PatLen )            

                        cout<<"KMP String Matching,pattern occurs with shift "<<i - PatLen + 1<<endl;            

}        

/*

** 由于時間關系，沒能将上述KMP算法的實作細節一一講清，以後有時間補上

*/

【參考文獻】

《Introduction to Algorithms》Second Edition

by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford .

     本文轉自Bill_Hoo 51CTO部落格，原文連結：http://blog.51cto.com/billhoo/411486，如需轉載請自行聯系原作者