作者： July 、 saturnma 時間； 二零一一年一月一日
-----------------------
本文參考：數據結構（c語言版） 李雲清等編著、算法導論
作者說明：本文寫的糟，日後此KMP 算法還會寫一個續集。為了讓本經典算法研究系列保持連貫性，特沒刪除本文。
引言：
在文本編輯中，我們經常要在一段文本中某個特定的位置找出 某個特定的字符或模式。
由此，便產生了字符串的匹配問題。
本文由簡單的字符串匹配算法開始，再到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算法
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
a0a1...ak-1ak=aj-kaj-k+1...aj-1aj
則對於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)過程.
下面給出一段計算覆蓋函數的代碼：
#include<iostream>
#include<string>
using namespace std;
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;
}
else
{
overlay_function[i] = -1;
