字元串模式比對——BF算法&KMP算法

在字元串模式比對的學習中，對于沒有學過的資料結構與算法的來講，可能首先就會想起将模式字元串和目标字元串逐個去比較，直到比對為止，這就學術上說的“樸素”算法，這算法的确可行，但是不高效，進而有了KMP的算法的出現，簡單來講KMP算法就是利用模式字元和比對過程的已知條件得出一個值，去跳過在樸素算法逐個比對過程中無必要的比對，進而達到高效的算法。雖然這是簡單的思路，但是KMP算法了解起來真的比較費勁，下面，我自己結合課件和網上各位大神的解釋，總結寫一下比較好懂的KMP算法解釋。

字元串模式比對指的是，找出特定的模式串在一個較長的字元串中出現的位置。

• 樸素的模式比對算法（BF(Brute Force)算法）

樸素模式比對算法的基本思想是窮舉法，即就是将目标串S的第一個字元與模式串P的第一個字元進行比對，若相等，則繼續比較S的第二個字元和P的第二個字元；若不相等，則比較S的第二個字元和P的第一個字元，依次比較下去，直到得出最後的比對結果（如圖1所示）。

圖1：樸素的比對方法示意

樸素的字元串模式比對算法：

view plaincopy to clipboardprint

1. /*  
2. 函數 int NaiveStringMatching(String T,String P)從目标T的首位位置開始模式比對，  
3. 用模式P比對T，尋找首個P子串并傳回其下标位置。若整個比對過程失敗 （模式P移動到目标T  
4. 尾部位置），則傳回負值。  
5. */ 
6. int NaiveStringMatching(const String &T,const String &P){  
7.     int i=0;                           //模式的下标變量   
8.     int j=0;                           //目标的下标變量   
9.     int pLen=P.length();               //模式的長度   
10.     int tLen=T.length();               //目标的長度   
11.     if (tLen<pLen)                     //如果目标比模式短，比對無法成功   
12.         return(-1);  
13.     while (i<pLen&&j<tLen){            //反複比較對應字元來開始比對   
14.         if (T[j]==P[i])  
15.             i++,j++;                   //繼續比較後續字元    
16.         else{                          //指針回溯到 下一首位，重新開始  
17.             j=j-i+1;  
18.             i=0;  
19.         }  
20.     }  
21.     if (i>=pLen)  
22.         return (j-pLen+1);  
23.     else 
24.         return (-1);  
25. } 

上面的代碼，T就是目标串，p是模式串，其實作思想也很簡單：

當T[j] == p[i]時，目标串和模式串的指針都向後移動一位，進行比對。而當T[j] != p[i]時，即比對不成功時，将目标串和模式串的指針同時回溯，i = 0 而目标串的指針j則回溯到這輪開始的下一個位置。

樸素的模式比對的算法複雜度是O( (n-m+1) * m)  n為目标串的長度，m為模式串長度。

從其實作思想上可以很容易的看出，造成該算法低效的地方是在比對不成功時主串和模式串的指針回溯上。

• KMP模式比對算法

為了避免指針的回溯,Knuth(D.E.Knuth)、Morris(J.H.Morris）和Pratt(V.R.Pratt）等人，發現其實每次右移的位數存在且與目标串無關，僅僅依賴模式本身，進而進行改進算法。

改進後的算法（簡稱為：KMP算法）的基本思想為：預先處理模式本身，分析其字元分布狀況，并為模式中的每一個字元計算失配時應該右移的位數。這就是所謂的字元串的特征向量。

字元串的特征向量是KMP算法的關鍵，而這個字元串的特征向量也稱為Next數組，是以如果我們可以得出這個Next數組就可以知道每一個字元失配時應該右移的位數。

而問題來了，這個所謂的Next數組（字元串的特征向量）怎麼樣可以求出？在解決這個問題之前，我們先來了解一下字元串的“字首子串”和“字尾子串”兩個概念。

• "字首子串"指除了最後一個字元以外，一個字元串的全部頭部組合
• "字尾子串"指除了第一個字元以外，一個字元串的全部尾部組合。

同時我們還來定義"字首子串"和"字尾子串"的最長的共有元素的長度為K值，稱為特征數，以"ABCDABD"為例：

       1、　"A"的字首和字尾都為空集，共有元素的長度為0；

　　2、　"AB"的字首為[A]，字尾為[B]，共有元素的長度為0；

　　3、　"ABC"的字首為[A, AB]，字尾為[BC, C]，共有元素的長度0；

　　4、　"ABCD"的字首為[A, AB, ABC]，字尾為[BCD, CD, D]，共有元素的長度為0；

　　5、　"ABCDA"的字首為[A, AB, ABC, ABCD]，字尾為[BCDA, CDA, DA, A]，共有元素為"A"，長度為1；

　　6、　"ABCDAB"的字首為[A, AB, ABC, ABCD, ABCDA]，字尾為[BCDAB, CDAB, DAB, AB, B]，共有元素為"AB"，長度為2；

　　到目前為止，應該可以了解特征數K值的求法，而所有的特征數組成就成為我們所求的Next數組（字元串的特征向量）。細心的可以發現模式串P "ABCDABD"中第一“A”下面沒有對應的特征數K值。其實此可以填上-1作為特征數，進而可以組成特征向量Next數組={-1,0，0，0，0，1,2}，至于為什麼是”-1“，而不是其他數呢？下面會有說明。

在說明為什麼是”-1“之前，先驗證之前說的Next數組就可以知道每一個字元失配時應該右移的位數，下面舉一例子以說明：

如果按照之前所說得樸素模式比對算法的話，最自然的反應是，将搜尋詞整個後移一位，再從頭逐個比較。

但是，我們已經在上面已經對模式串P進行分析了，還得出了Next數組（字元串的特征向量），不必再去逐個比較，

已知空格與D不比對時，前面六個字元"ABCDAB"是比對的。由失配的”D”對應的特征數K值為2，對于的模式串位置為6，即可按照以下公式可算出向後移動的位數：

移動位數 = 失配字元所在的位置i - 對應特征數K

即可移動位數=6-2=4，是以應該向後移動 4 位。同理，當失配時，即可計算出移動位數，直到比對為止。

此刻根據公式，即可反向推出為什麼首字元對應為“-1”，可以假設當模式串P與目标串一開始就不比對，易知需要移動一位，

即1（移動位數）=0（失配字元所在的位置i）-對應特征數K

得對應特征數K=-1；可見為什麼是“-1”即可得出。

由此可以得出模式P的特征向量Next的計算公式：

下面還是以"ABCDABD"為例解釋一下計算公式的使用：

給定的字元串叫做模式串P。i表示next函數的參數，其值是從1到n。而k則表示一種情況下的next函數值。P表示其中的某個字元，下标從1開始。看等式左右對應的字元是否相等。

i=0時，next[0]=-1；

i=1時，k的取值為(0,1)的開區間，是以整數k是不存在的，那就是第三種情況，next[1]=0；

i=2時，k的取值為（0，2）的開區間，k從最大的開始取值，然後帶入含p的式子中驗證等式是否成立，不成立k取第二大的值。現在是k=1，将k導入p的式中得，P0=P1，即“A”=“B”，顯然不成立，舍去。k再取值就超出範圍了，是以next[2]不屬于第二種情況，那就是第三種了，即next[2]=0；

i=3時，k的取值為（0，3）的開區間，先取k=2，将k導入p的式子中得，P0P1=P1P2，不成立。 再取k=1，得P0=P2，不成立。那就是第三種了，即next[3]=0；

i=4時，k的取值為（0，4）的開區間，先取k=3，将k導入p的式子中得，P0P1P2=P1P2P3，不成立。 再取k=2，得P0P1=P2P3，不成立。 再取k=1，得P0=P3，不成立。是以next[4]=0；

i=5時，k的取值為（1，5）的開區間，先取k=4，将k導入p的式子中得，P0P1P2P3=P1P2P3P4，不成立。 取k=3，得P0P1P2=P2P3P4，不成立。再取k=2，将k導入p的式子中得，P0P1=P3P4，不成立。再取k=1，将k導入p的式子中得，P0=P4，成立。那就是第二種了 ，是以next[5]=1；

i=6時，k的取值為（1，6）的開區間，先取k=5，将k導入p的式子中得，P0P1P2P3P4=P1P2P3P4P5，不成立。 取k=4，得P0P1P2P3=P2P3P4P5，不成立。再取k=3，将k導入p的式子中得，P0P1P2=P3P4P5，不成立。再取k=2，将k導入p的式子中得，P0P1=P4P5，成立。那就是第二種了 ，是以next[6]=2；

即可得下表

其實，在計算的時候就會發現，這也是和之前說得計算特征數K值是一樣的思路，進而也得出Next[i]數組={-1，0，0，0，0，1，2}，是以當熟悉的時候就可以很快求出模式字元串的Next數組（字元串的特征向量）。

下面再以另外一例子來該next數組還可進一步優化。

目标字元串T為：abacaabaccabacabaa

模式字元串P為：abacab

next向量根據上面的方法可以求出如下表：

  在上圖可以知道，當進行第6次比較的時候，發現此刻是失配的，按照之前的“移動位數 = 失配字元所在的位置i - 對應特征數K”可以得出5-1=4，即右移4位，再次進行第7次比較，其他如此類推進行比較。

這裡的确是KMP算法的思想，已經利用模式字元串的特征來跳過不必要的比較，但是細心的可以發現，在第6次比較的時候，目标字元串T中的a的确不等于模式字元串P的j=5位置的b,同時模式字元串P的j=5位置的b，我們可以根據已知的模式字元串P特征，得出j=1位置的b等于j=5位置的b，即可知道j=1位置的b不會等于目标字元串T中的a，當右移4位再次比較，已經沒有必要，此刻應該再右移進行比較，如下圖。

當 i = 0時，令next[i] = -1

其實，若pk = pi ，則有pk 不等于Tj；此時應再右移，使pnext[k]與 Tj 比較，故

第2步可進一步優化為：

view plaincopy to clipboardprint

1. if  (pk==pi)    
2. next[i] = next[k];  
3.  else   next[i] = k; 

可以得

簡單說明優化Next求法：

i = 0時，依然是-1，而i=1時候，k為0，代入PK得PK=a，而Pi=b，顯然是不等

同理即求出其他關系，在這裡說明一下，當PK vs Pi 的關系不等的時候，優化後的K值還是優化前的K值，而PK vs Pi 的關系相等，即優化後的K值為PK對應的k值。

計算字元串特征向量（優化）代碼：

view plaincopy to clipboardprint

1. /*  
2. 計算字元串特征向量（優化版）   
3. */ 
4. int *findNext(String P){  
5.     int i = 0;  
6.     int k = -1;  
7.     int m = P.length();                   //m為字元串P的長度   
8.     assert(m>0);                          // 若m=0,退出   
9.     int * next = new int [m];            // 動态存儲區開辟整數數組   
10.     assert (next != 0);                 //若開辟存儲區域失敗，退出   
11.     next[0]=-1;  
12.     while(i<m){                          //計算i=1...m-1的next值   
13.         while (k>=0&&P[i]!=P[k])  
14.             k-next[k];  
15.         i++;  
16.         k++;  
17.         if(i==m) break;  
18.         if(P[i]==P[k])  
19.             next[i]==next[k];         //P[i]和P[k]相等，優化     
20.         else 
21.             next[i]=k;               //不需要優化，就是位置i的首尾子串的長度   
22.     }   
23.     return next;  
24. } 

到目前為止，整個KMP算法的思路已經很清楚。

KMP算法代碼：

view plaincopy to clipboardprint

1. /*  
2. KMP模式比對算法的實作   
3. */ 
4. int KMPStrMatching(const String &T,const String &P,int *N){    
5.     int i=0;                           //模式的下标變量   
6.     int j=0;                           //目标的下标變量   
7.     int pLen=P.length();              //模式的長度   
8.     int tLen=T.length();              //目标的長度   
9.     if (tLen<pLen)                    //如果目标比模式短，比對無法成功   
10.         return(-1);  
11.     while (i<pLen&&j<tLen){           //反複比較對應字元來開始比對   
12.         if(i==-1||T[j]==P[i])  
13.             i++,j++;  
14.         else 
15.             i=N[i];  
16.     }  
17.     if (i>plen)  
18.         return (j-plen+1);  
19.     else 
20.         return (-1);  
21. } 

kmp的應用優勢:

①高效，O(m+n)的線性最壞時間複雜度；

②無需回朔通路待比對字元串S.

總結:

小弟剛剛開始學資料結構與算法，可能文章某些地方有所欠缺與不足，請忘原諒并多加指點，同時本文參考了阮一峰，崔成龍和waytofall等的博文，同時在此基礎上有所修改,總體思路還是一樣，為了表示尊重，已經在最後列出原博文位址。最後感悟的是，站在大神的肩膀上看得更遠。

參考資料：

[1]張銘 王騰蛟 趙海燕 資料結構與算法 高等教育出版社

[2] 阮一峰 http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

[3] 崔成龍 http://blog.csdn.net/xiaoxian8023/article/details/8134292

[4] waytofall http://www.cnblogs.com/waytofall/archive/2012/10/27/2742163.html