教你初步了解KMP算法
作者： July 、saturnma、上善若水。
-----------------------
引言：
在文本編輯中，我們經常要在一段文本中某個特定算法的位置找出 某個特定的字元或模式。
由此，便産生了字元串的比對問題。
本文由簡單的字元串比對算法開始，再到KMP，由淺入深，教你從頭到尾徹底了解KMP算法。
來看算法導論一書上關于此字元串問題的定義：
假設文本是一個長度為n的數組T[1...n]，模式是一個長度為m<=n的數組P[1....m]。
進一步假設P和T的元素都是屬于有限字母表Σ.中的字元。
依據上圖，再來解釋下字元串比對問題。目标是找出所有在文本T=abcabaabcaabac中的模式P=abaa所有出現。
該模式僅在文本中出現了一次，在位移s=3處。位移s=3是有效位移。
第一節、簡單的字元串比對算法
簡單的字元串比對算法用一個循環來找出所有有效位移，
該循環對n-m+1個可能的每一個s值檢查條件P[1....m]=T[s+1....s+m]。
NAIVE-STRING-MATCHER(T, P)
1 n ← length[T]
2 m ← length[P]
3 for s ← 0 to n - m
4 do if P[1 ‥ m] = T[s + 1 ‥ s + m]
//對n-m+1個可能的位移s中的每一個值，比較相應的字元的循環必須執行m次。
5 then print "Pattern occurs with shift" s
簡單字元串比對算法，上圖針對文本T=acaabc 和模式P=aab。
上述第4行代碼，n-m+1個可能的位移s中的每一個值，比較相應的字元的循環必須執行m次。
是以，在最壞情況下，此簡單模式比對算法的運作時間為O（(n-m+1)m）。
--------------------------------
下面我再來舉個具體例子，并給出一具體運作程式：
對于目的字串target是banananobano,要比對的字串pattern是nano,的情況，
下面是比對過程，原理很簡單，隻要先和target字串的第一個字元比較，
如果相同就比較下一個，如果不同就把pattern右移一下，
之後再從pattern的每一個字元比較，這個算法的運作過程如下圖。
//index表示的每n次比對的情形。
#include<iostream>
#include<string>
using namespace std;
int match(const string& target,const string& pattern)
{
int target_length = target.size();
int pattern_length = pattern.size();
int target_index = 0;
int pattern_index = 0;
while(target_index < target_length && pattern_index < pattern_length)
{
if(target[target_index]==pattern[pattern_index])
{
++target_index;
++pattern_index;
}
else
target_index -= (pattern_index-1);
pattern_index = 0;
}
if(pattern_index == pattern_length)
return target_index - pattern_length;
else
return -1;
}
int main()
cout<<match("banananobano","nano")<<endl;
return 0;
//運作結果為4。
上面的算法進間複雜度是O(pattern_length*target_length),
我們主要把時間浪費在什麼地方呢，
觀查index =2那一步，我們已經比對了3個字元，而第4個字元是不比對的，這時我們已經比對的字元序列是nan,
此時如果向右移動一位，那麼nan最先比對的字元序列将是an,這肯定是不能比對的，
之後再右移一位，比對的是nan最先比對的序列是n,這是可以比對的。
如果我們事先知道pattern本身的這些資訊就不用每次比對失敗後都把target_index回退回去，
這種回退就浪費了很多不必要的時間，如果能事先計算出pattern本身的這些性質，
那麼就可以在失配時直接把pattern移動到下一個可能的位置，
把其中根本不可能比對的過程省略掉，
如上表所示我們在index=2時失配，此時就可以直接把pattern移動到index=4的狀态，
kmp算法就是從此出發。
第二節、KMP算法
2.1、 覆寫函數(overlay_function)
覆寫函數所表征的是pattern本身的性質，可以讓為其表征的是pattern從左開始的所有連續子串的自我覆寫程度。
比如如下的字串，abaabcaba
由于計數是從0始的，是以覆寫函數的值為0說明有1個比對，對于從0還是從來開始計數是偏好問題，
具體請自行調整，其中-1表示沒有覆寫，那麼何為覆寫呢，下面比較數學的來看一下定義，比如對于序列
a0a1...aj-1 aj
要找到一個k,使它滿足
a0a1...ak-1ak=aj-kaj-k+1...aj-1aj
而沒有更大的k滿足這個條件，就是說要找到盡可能大k,使pattern前k字元與後k字元相比對，k要盡可能的大，
原因是如果有比較大的k存在，而我們選擇較小的滿足條件的k，
那麼當失配時，我們就會使pattern向右移動的位置變大，而較少的移動位置是存在比對的，這樣我們就會把可能比對的結果丢失。
比如下面的序列，
在紅色部分失配，正确的結果是k=1的情況，把pattern右移4位，如果選擇k=0,右移5位則會産生錯誤。
計算這個overlay函數的方法可以采用遞推，可以想象如果對于pattern的前j個字元，如果覆寫函數值為k
則對于pattern的前j+1序列字元，則有如下可能
⑴ pattern[k+1]==pattern[j+1] 此時overlay(j+1)=k+1=overlay(j)+1
⑵ pattern[k+1]≠pattern[j+1] 此時隻能在pattern前k+1個子符組所的子串中找到相應的overlay函數，h=overlay(k),如果此時pattern[h+1]==pattern[j+1],則overlay(j+1)=h+1否則重複(2)過程.
下面給出一段計算覆寫函數的代碼：
void compute_overlay(const string& pattern)
const int pattern_length = pattern.size();
int *overlay_function = new int[pattern_length];
int index;
overlay_function[0] = -1;
for(int i=1;i<pattern_length;++i)
index = overlay_function[i-1];
//store previous fail position k to index;
while(index>=0 && pattern[i]!=pattern[index+1])
index = overlay_function[index];
if(pattern[i]==pattern[index+1])
overlay_function[i] = index + 1;
overlay_function[i] = -1;
for(i=0;i<pattern_length;++i)
cout<<overlay_function[i]<<endl;
delete[] overlay_function;
string pattern = "abaabcaba";
compute_overlay(pattern);
運作結果為：
-1
1
2
Press any key to continue
-------------------------------------
2.2、kmp算法
有了覆寫函數，那麼實作kmp算法就是很簡單的了，我們的原則還是從左向右比對，但是當失配發生時，我們不用把target_index向回移動，target_index前面已經比對過的部分在pattern自身就能展現出來，隻要動pattern_index就可以了。
當發生在j長度失配時，隻要把pattern向右移動j-overlay(j)長度就可以了。
如果失配時pattern_index==0，相當于pattern第一個字元就不比對，
這時就應該把target_index加1，向右移動1位就可以了。
ok，下圖就是KMP算法的過程（紅色即是采用KMP算法的執行過程）：
另一作者saturnman發現，在上述KMP比對過程圖中，index=8和index=11處畫錯了。還有，anaven也早已發現，index=3處也畫錯了。非常感謝。但圖已無法修改，見諒。
KMP 算法可在O（n+m）時間内完成全部的串的模式比對工作。
ok，最後給出KMP算法實作的c++代碼：
#include<vector>
int kmp_find(const string& target,const string& pattern)
const int target_length = target.size();
int * overlay_value = new int[pattern_length];
overlay_value[0] = -1;
int index = 0;
index = overlay_value[i-1];
while(index>=0 && pattern[index+1]!=pattern[i])
index = overlay_value[index];
if(pattern[index+1]==pattern[i])
overlay_value[i] = index +1;
overlay_value[i] = -1;
//match algorithm start
while(pattern_index<pattern_length&&target_index<target_length)
else if(pattern_index==0)
pattern_index = overlay_value[pattern_index-1]+1;
if(pattern_index==pattern_length)
return target_index-pattern_index;
delete [] overlay_value;
string source = " annbcdanacadsannannabnna";
string pattern = " annacanna";
cout<<kmp_find(source,pattern)<<endl;
//運作結果為 -1.
第三節、kmp算法的來源
kmp如此精巧，那麼它是怎麼來的呢，為什麼要三個人合力才能想出來。其實就算沒有kmp算法，人們在字元比對中也能找到相同高效的算法。這種算法,最終相當于kmp算法，隻是這種算法的出發點不是覆寫函數，不是直接從比對的内在原理出發，而使用此方法的計算的覆寫函數過程式複雜且不易被了解，但是一但找到這個覆寫函數，那以後使用同一pattern比對時的效率就和kmp一樣了，其實這種算法找到的函數不應叫做覆寫函數，因為在尋找過程中根本沒有考慮是否覆寫的問題。
說了這麼半天那麼這種方法是什麼呢，這種方法是就大名鼎鼎的确定的有限自動機(Deterministic finite state automaton DFA),DFA可識别的文法是3型文法，又叫正規文法或是正則文法，既然可以識别正則文法，那麼識别确定的字串肯定不是問題(确定字串是正則式的一個子集)。對于如何構造DFA,是有一個完整的算法，這裡不做介紹了。在識别确定的字串時使用DFA實在是大材小用，DFA可以識别更加通用的正規表達式，而用通用的建構DFA的方法來識别确定的字串，那這個overhead就顯得太大了。
kmp算法的可貴之處是從字元比對的問題本身特點出發，巧妙使用覆寫函數這一表征pattern自身特點的這一概念來快速直接生成識别字串的DFA,是以對于kmp這種算法，了解這種算法高中數學就可以了，但是如果想從無到有設計出這種算法是要求有比較深的數學功底的。
第四節、精确字元比對的常見算法的解析
KMP算法：
KMP就是串比對算法
運用自動機原理
比如說
我們在S中找P
設P＝{ababbaaba}
我們将P對自己比對
下面是求的過程:{依次記下比對失敗的那一位}
[2]ababbaaba
.......ababbaaba[1]
[3]ababbaaba
.........ababbaaba[1]
[4]ababbaaba
.........ababbaaba[2]
[5]ababbaaba
.........ababbaaba[3]
[6]ababbaaba
................ababbaaba[1]
[7]ababbaaba
................ababbaaba[2]
[8]ababbaaba
..................ababbaaba[2]
[9]ababbaaba
..................ababbaaba[3]
得到Next數組『0,1,1,2,3,1,2,2,3』
主過程：
[1]i:=1 j:=1
[2]若(j>m)或(i>n)轉[4]否則轉[3]
[3]若j=0或a[i]=b[j]則【inc(i)inc(j)轉[2]】否則【j:=next[j]轉2】
[4]若j>m則return(i-m)否則return -1;
若傳回－1表示失敗，否則表示在i-m處成功
BM算法也是一種快速串比對算法，KMP算法的主要差別是比對操作的方向不同。雖然T右移的計算方法卻發生了較大的變化。
為友善讨論，T＝＂dist ：ｃ－＞｛dist稱為滑動距離函數，它給出了正文中可能出現的任意字元在模式中的位置。函數 m – j j為 dist（m+1 若c = tm
例如，pattern＂，則p）a）t）dist（= 2，r）n）BM算法的基本思想是：假設将主串中自位置i + dist(si)位置開始重新進行新一輪的比對，其效果相當于把模式和主串向右滑過一段距離si），即跳過si）個字元而無需進行比較。
下面是一個S =＂T=＂BM算法可以大大加快串比對的速度。
下面是KMP算法部分，把調用BM函數便可。
#include <iostream>
int Dist(char *t,char ch)
int len = strlen(t);
int i = len - 1;
if(ch == t[i])
return len;
i--;
while(i >= 0)
{
if(ch == t[i])
return len - 1 - i;
else
i--;
}
return len;
int BM(char *s,char *t)
int n = strlen(s);
int m = strlen(t);
int i = m-1;
int j = m-1;
while(j>=0 && i<n)
if(s[i] == t[j])
{
j--;
}
i += Dist(t,s[i]);
j = m-1;
if(j < 0)
return i+1;
return -1;
}
Horspool算法
這個算法是由R.Nigel Horspool在1980年提出的。其滑動思想非常簡單，就是從後往前比對模式串，若在某一位失去比對，此位對應的文本串字元為c，那就将模式串向右滑動，使模式
串之前最近的c對準這一位，再從新從後往前檢查。那如果之前找不到c怎麼辦？那好極了，直接将整個模式串滑過這一位。
例如：
文本串：abdabaca
模式串：baca
倒數第2位失去比對，模式串之前又沒有d，那模式串就可以整個滑過，變成這樣：
模式串： baca
發現倒數第1位就失去比對，之前1位有c，那就向右滑動1位：
模式串： baca
實作代碼：
#include <vector>
#include <string>
#include <cstdlib>
int Horspool_match(const string & S,const string & M,int pos)
int S_len = S.size();
int M_len = M.size();
int Mi = M_len-1,Si= pos+Mi; //這裡的串的第1個元素下标是0
if( (S_len-pos) < M_len )
return -1;
while ( (Mi>-1) && (Si<S_len) )
{
if (S[Si] == M[Mi])
{
--Mi;
--Si;
}
else
do
{
Mi--;
}
while( (S[Si]!=M[Mi]) || (Mi>-1) );
Mi = M_len - 1;
Si += M_len - 1;
}
if(Si < S_len)
return(Si + 1);
else
return -1;
int main( )
string S="abcdefghabcdefghhiijiklmabc";
string T="hhiij";
int pos = Horspool_match(S,T,3);
cout<<"/n"<<pos<<endl;
system("pause");
return 0;
}