[[121931]]

本文參考：數(shù)據(jù)結(jié)構(gòu)（c語言版） 李云清等編著、算法導(dǎo)論

引言：

在文本編輯中，我們經(jīng)常要在一段文本中某個(gè)特定的位置找出 某個(gè)特定的字符或模式。

由此，便產(chǎn)生了字符串的匹配問題。

本文由簡(jiǎn)單的字符串匹配算法開始，經(jīng)Rabin-Karp算法，***到KMP算法，教你從頭到尾徹底理解KMP算法。

來看算法導(dǎo)論一書上關(guān)于此字符串問題的定義：

假設(shè)文本是一個(gè)長(zhǎng)度為n的數(shù)組T[1...n]，模式是一個(gè)長(zhǎng)度為m<=n的數(shù)組P[1....m]。

進(jìn)一步假設(shè)P和T的元素都是屬于有限字母表Σ.中的字符。

依據(jù)上圖，再來解釋下字符串匹配問題。目標(biāo)是找出所有在文本T=abcabaabcaabac中的模式P=abaa所有出現(xiàn)。

該模式僅在文本中出現(xiàn)了一次，在位移s=3處。位移s=3是有效位移。

一、簡(jiǎn)單的字符串匹配算法

簡(jiǎn)單的字符串匹配算法用一個(gè)循環(huán)來找出所有有效位移，

該循環(huán)對(duì)n-m+1個(gè)可能的每一個(gè)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]

//對(duì)n-m+1個(gè)可能的位移s中的每一個(gè)值，比較相應(yīng)的字符的循環(huán)必須執(zhí)行m次。

5 then print "Pattern occurs with shift" s

簡(jiǎn)單字符串匹配算法，上圖針對(duì)文本T=acaabc 和模式P=aab。

上述第4行代碼，n-m+1個(gè)可能的位移s中的每一個(gè)值，比較相應(yīng)的字符的循環(huán)必須執(zhí)行m次。

所以，在最壞情況下，此簡(jiǎn)單模式匹配算法的運(yùn)行時(shí)間為O（(n-m+1)m）。

--------------------------------

下面我再來舉個(gè)具體例子，并給出一具體運(yùn)行程序：

對(duì)于目的字串target是banananobano,要匹配的字串pattern是nano,的情況，

下面是匹配過程，原理很簡(jiǎn)單，只要先和target字串的***個(gè)字符比較，

如果相同就比較下一個(gè)，如果不同就把pattern右移一下，

之后再從pattern的每一個(gè)字符比較，這個(gè)算法的運(yùn)行過程如下圖。

//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; 
} 
//運(yùn)行結(jié)果為4。

上面的算法進(jìn)間復(fù)雜度是O(pattern_length*target_length),

我們主要把時(shí)間浪費(fèi)在什么地方呢，

觀查index =2那一步，我們已經(jīng)匹配了3個(gè)字符，而第4個(gè)字符是不匹配的，這時(shí)我們已經(jīng)匹配的字符序列是nan,

此時(shí)如果向右移動(dòng)一位，那么nan***匹配的字符序列將是an,這肯定是不能匹配的，

之后再右移一位，匹配的是nan***匹配的序列是n,這是可以匹配的。

如果我們事先知道pattern本身的這些信息就不用每次匹配失敗后都把target_index回退回去，

這種回退就浪費(fèi)了很多不必要的時(shí)間，如果能事先計(jì)算出pattern本身的這些性質(zhì)，

那么就可以在失配時(shí)直接把pattern移動(dòng)到下一個(gè)可能的位置，

把其中根本不可能匹配的過程省略掉，

如上表所示我們?cè)趇ndex=2時(shí)失配，此時(shí)就可以直接把pattern移動(dòng)到index=4的狀態(tài)，

kmp算法就是從此出發(fā)。

二、KMP算法

1、 覆蓋函數(shù)(overlay_function)

覆蓋函數(shù)所表征的是pattern本身的性質(zhì)，可以讓為其表征的是pattern從左開始的所有連續(xù)子串的自我覆蓋程度。

比如如下的字串，abaabcaba

由于計(jì)數(shù)是從0始的，因此覆蓋函數(shù)的值為0說明有1個(gè)匹配，對(duì)于從0還是從來開始計(jì)數(shù)是偏好問題，

具體請(qǐng)自行調(diào)整，其中-1表示沒有覆蓋，那么何為覆蓋呢，下面比較數(shù)學(xué)的來看一下定義，比如對(duì)于序列

a0a1...aj-1 aj

要找到一個(gè)k,使它滿足

a0a1...ak-1ak=aj-kaj-k+1...aj-1aj

而沒有更大的k滿足這個(gè)條件，就是說要找到盡可能大k,使pattern前k字符與后k字符相匹配，k要盡可能的大，

原因是如果有比較大的k存在，而我們選擇較小的滿足條件的k，

那么當(dāng)失配時(shí)，我們就會(huì)使pattern向右移動(dòng)的位置變大，而較少的移動(dòng)位置是存在匹配的，這樣我們就會(huì)把可能匹配的結(jié)果丟失。

比如下面的序列，

在紅色部分失配，正確的結(jié)果是k=1的情況，把pattern右移4位，如果選擇k=0,右移5位則會(huì)產(chǎn)生錯(cuò)誤。

計(jì)算這個(gè)overlay函數(shù)的方法可以采用遞推，可以想象如果對(duì)于pattern的前j個(gè)字符，如果覆蓋函數(shù)值為k

a0a1...ak-1ak=aj-kaj-k+1...aj-1aj

則對(duì)于pattern的前j+1序列字符，則有如下可能

⑴ pattern[k+1]==pattern[j+1] 此時(shí)overlay(j+1)=k+1=overlay(j)+1

⑵ pattern[k+1]≠pattern[j+1] 此時(shí)只能在pattern前k+1個(gè)子符組所的子串中找到相應(yīng)的overlay函數(shù)，h=overlay(k),如果此時(shí)pattern[h+1]==pattern[j+1],則overlay(j+1)=h+1否則重復(fù)(2)過程.

下面給出一段計(jì)算覆蓋函數(shù)的代碼：

 

#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; 
} 
} 
for(i=0;i<pattern_length;++i) 
{ 
cout<<overlay_function[i]<<endl; 
} 
delete[] overlay_function; 
} 
int main() 
{ 
string pattern = "abaabcaba"; 
compute_overlay(pattern); 
return 0; 
} 

運(yùn)行結(jié)果為：

-1

-1

0

0

1

-1

0

1

2

Press any key to continue

-------------------------------------

2、kmp算法

有了覆蓋函數(shù)，那么實(shí)現(xiàn)kmp算法就是很簡(jiǎn)單的了，我們的原則還是從左向右匹配，但是當(dāng)失配發(fā)生時(shí)，我們不用把target_index向回移 動(dòng)，target_index前面已經(jīng)匹配過的部分在pattern自身就能體現(xiàn)出來，只要?jiǎng)觩attern_index就可以了。

當(dāng)發(fā)生在j長(zhǎng)度失配時(shí)，只要把pattern向右移動(dòng)j-overlay(j)長(zhǎng)度就可以了。

如果失配時(shí)pattern_index==0，相當(dāng)于pattern***個(gè)字符就不匹配，

這時(shí)就應(yīng)該把target_index加1，向右移動(dòng)1位就可以了。

ok，下圖就是KMP算法的過程（紅色即是采用KMP算法的執(zhí)行過程）：

ok，***給出KMP算法實(shí)現(xiàn)的c++代碼：

#include<iostream> 
#include<string> 
#include<vector> 
using namespace std; 
int kmp_find(const string& target,const string& pattern) 
{ 
const int target_length = target.size(); 
const int pattern_length = pattern.size(); 
int * overlay_value = new int[pattern_length]; 
overlay_value[0] = -1; 
int index = 0; 
for(int i=1;i<pattern_length;++i) 
{ 
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; 
} 
else 
{ 
overlay_value[i] = -1; 
} 
} 
//match algorithm start 
int pattern_index = 0; 
int target_index = 0; 
while(pattern_index<pattern_length&&target_index<target_length) 
{ 
if(target[target_index]==pattern[pattern_index]) 
{ 
++target_index; 
++pattern_index; 
} 
else if(pattern_index==0) 
{ 
++target_index; 
} 
else 
{ 
pattern_index = overlay_value[pattern_index-1]+1; 
} 
} 
if(pattern_index==pattern_length) 
{ 
return target_index-pattern_index; 
} 
else 
{ 
return -1; 
} 
delete [] overlay_value; 
} 
int main() 
{ 
string source = " annbcdanacadsannannabnna"; 
string pattern = " annacanna"; 
cout<<kmp_find(source,pattern)<<endl; 
return 0; 
} 
//運(yùn)行結(jié)果為 -1. 

三、kmp算法的來源

kmp如此精巧，那么它是怎么來的呢，為什么要三個(gè)人合力才能想出來。其實(shí)就算沒有kmp算法，人們?cè)谧址ヅ渲幸材苷业较嗤咝У乃惴?。這種算法,最終 相當(dāng)于kmp算法，只是這種算法的出發(fā)點(diǎn)不是覆蓋函數(shù)，不是直接從匹配的內(nèi)在原理出發(fā)，而使用此方法的計(jì)算的覆蓋函數(shù)過程序復(fù)雜且不易被理解，但是一但找 到這個(gè)覆蓋函數(shù)，那以后使用同一pattern匹配時(shí)的效率就和kmp一樣了，其實(shí)這種算法找到的函數(shù)不應(yīng)叫做覆蓋函數(shù)，因?yàn)樵趯ふ疫^程中根本沒有考慮是 否覆蓋的問題。

說了這么半天那么這種方法是什么呢，這種方法是就大名鼎鼎的確定的有限自動(dòng)機(jī)(Deterministic finite state automaton DFA),DFA可識(shí)別的文法是3型文法，又叫正規(guī)文法或是正則文法，既然可以識(shí)別正則文法，那么識(shí)別確定的字串肯定不是問題(確定字串是正則式的一個(gè)子 集)。對(duì)于如何構(gòu)造DFA,是有一個(gè)完整的算法，這里不做介紹了。在識(shí)別確定的字串時(shí)使用DFA實(shí)在是大材小用，DFA可以識(shí)別更加通用的正則表達(dá)式，而 用通用的構(gòu)建DFA的方法來識(shí)別確定的字串，那這個(gè)overhead就顯得太大了。

kmp算法的可貴之處是從字符匹配的問題本身特點(diǎn)出發(fā)，巧妙使用覆蓋函數(shù)這一表征pattern自身特點(diǎn)的這一概念來快速直接生成識(shí)別字串的DFA,因此對(duì)于kmp這種算法，理解這種算法高中數(shù)學(xué)就可以了，但是如果想從無到有設(shè)計(jì)出這種算法是要求有比較深的數(shù)學(xué)功底的。

原文：http://www.2cto.com/kf/201104/87381.html

作者聲明：個(gè)人July 對(duì)此24個(gè)經(jīng)典算法系列，享有版權(quán)，轉(zhuǎn)載請(qǐng)注明出處。