KMP算法-關(guān)鍵詞搜索完整匹配與部分匹配
KMP檢索詞算法（搜索詞及部分匹配值）如下圖如示：
一開(kāi)始我一直以為單個(gè)字符進(jìn)行計(jì)算，后來(lái)經(jīng)過(guò)查詢資料發(fā)現(xiàn)我錯(cuò)了，每個(gè)字符下面記錄的部分匹配值不是這單個(gè)字符的值，而是從開(kāi)頭字符到此字符這個(gè)字符串的值，這樣說(shuō)可能有點(diǎn)抽象，下面以上圖為例詳細(xì)介紹一下
為了方便說(shuō)明這里把搜索詞記為：P={ABCDABD}
1，P[0]表示“A”，其完全前后綴都是空，所以其部分匹配值為0
2，P[1]表示“AB”，其完全前綴為{空，A}，完全后綴為{B，空}，前后綴中只有空相同，所以AB(即P[1])的匹配值為0
3，P[2]表示“ABC”，其完全前綴為{空，A，AB}，完全后綴為{BC，B，空}，前后綴中只有空相同，所以ABC(即P[2])的匹配值為0
4，P[3]表示“ABCD”，其完全前綴為{空，A，AB，ABC}，完全后綴為{BCD，CD，D，空}，前后綴中只有空相同，所以ABCD(即P[3])的匹配值為0
5，P[4]表示“ABCDA”，其完全前綴為{空，A，AB，ABC，ABCD}，完全后綴為{BCDA，CDA，DA，A，空}，前后綴中都有{A}長(zhǎng)度為1，所以ABCDA(即P[4])的匹配值為1
6，P[5]表示“ABCDAB”其完全前綴為{空，A，AB，ABC，ABCD，ABCDA}，完全后綴為{BCDAB，CDAB，DAB，AB，B，空}，前后綴中都有{AB}長(zhǎng)度為2，所以ABCDAB(即P[5])的匹配值為2
7，P[6]表示“ABCDABD”其完全前綴為{空，A，AB，ABC，ABCD，ABCDA，ABCDAB}，完全后綴為{BCDABD，CDABD，DABD，ABD，BD，D，空}，前后綴中只有空相同，所以ABCDABD(即P[6])的匹配值為0
說(shuō)明：
P[i]表示能匹配的字符串，部分匹配值計(jì)算的是能匹配的字符串對(duì)應(yīng)該的值，例如上面的P[5]表示的是如果匹配了字符串“ABCDAB”，則這個(gè)字符串對(duì)應(yīng)的部分匹配值為2，而不是第二個(gè)字符B的部分匹配值
為了方便操作，字符串的部分匹配值都對(duì)應(yīng)到字符串的Z后一個(gè)字符，這樣即方便記錄也方便查詢
另外，
"部分匹配值"就是"前綴"和"后綴"的Z長(zhǎng)的共有元素的長(zhǎng)度，這個(gè)已經(jīng)在阮總的文件中解釋，這里再?gòu)?qiáng)調(diào)一點(diǎn)，其前后綴都是表示完全前后綴，即不包含自身的前綴或者后綴。
做網(wǎng)絡(luò)營(yíng)銷的都應(yīng)該知道，競(jìng)價(jià)推廣是網(wǎng)絡(luò)營(yíng)銷的首選手段，而要做好中國(guó)市場(chǎng)的廣告競(jìng)價(jià)推廣就必須要了解百度競(jìng)價(jià)。細(xì)心研究過(guò)百度競(jìng)價(jià)對(duì)網(wǎng)站業(yè)績(jī)提升是有很大的幫助。今天我就借助馬海祥博客的平臺(tái)跟大家淺談一下百度競(jìng)價(jià)，首先我們先談一下百度競(jìng)價(jià)中的四種關(guān)鍵詞匹配方式：短語(yǔ)匹配、廣泛匹配、精確匹配和否定匹配。
百度競(jìng)價(jià)的匹配方式組成：
短語(yǔ)匹配：匹配條件是搜索關(guān)鍵詞完全包含推廣關(guān)鍵詞，而且包含的部分與推廣關(guān)鍵詞字面完全一致時(shí)(順序不變，無(wú)間隔)才觸發(fā)，用于比較精確的匹配限制。短語(yǔ)匹配將限制只有網(wǎng)民搜索那些僅在字面上與關(guān)鍵詞高度相關(guān)的搜索詞時(shí)才能展現(xiàn)對(duì)應(yīng)的推廣信息。
例如：在短語(yǔ)匹配情況下，推廣關(guān)鍵詞“牛奶”與“購(gòu)買牛奶”、“嬰兒牛奶”、“牛奶價(jià)格”匹配，而與“牛奶米粉”不匹配。
優(yōu)勢(shì)：與精確匹配相比更為靈活且能獲得更多的潛在客戶訪問(wèn)，與廣泛匹配相比則有更強(qiáng)的針對(duì)性且可能有更高的轉(zhuǎn)化率。
劣勢(shì)：獲得的展示次數(shù)介于廣泛匹配與精確匹配之間，轉(zhuǎn)化率沒(méi)有精確匹配高。
廣泛匹配：匹配條件是搜索關(guān)鍵詞完全包含推廣關(guān)鍵詞，允許包含部分字面順序顛倒或有間隔，是Z寬泛的匹配方式，也是默認(rèn)的匹配方式。系統(tǒng)有可能對(duì)匹配條件進(jìn)行延伸，擴(kuò)展至關(guān)鍵詞的同義詞、近義詞、相關(guān)詞、以及包含關(guān)鍵詞的短語(yǔ)等。
例如：在廣泛匹配情況下，推廣關(guān)鍵詞“牛奶”可能與“牛奶米粉”匹配。
優(yōu)勢(shì)：是一種既進(jìn)行高針對(duì)性的投放、又接觸廣泛受眾群體的有效方法，能夠?yàn)榭蛻魩ジ嗟臐撛谟脩粼L問(wèn)。
劣勢(shì)：點(diǎn)擊訪問(wèn)的針對(duì)性不足，轉(zhuǎn)化率不如精確匹配和短語(yǔ)匹配。有可能會(huì)帶來(lái)大量點(diǎn)擊，觸發(fā)較多的點(diǎn)擊消費(fèi)。
精確匹配：匹配條件是在搜索關(guān)鍵詞與推廣關(guān)鍵詞二者字面完全一致時(shí)才觸發(fā)的限定條件，用于精確嚴(yán)格的匹配限制。使用精確匹配時(shí)，若搜索詞中包含其他詞語(yǔ)，或搜索詞與關(guān)鍵詞的詞語(yǔ)順序不同，均不會(huì)展現(xiàn)對(duì)應(yīng)的創(chuàng)意。
例如：精確匹配時(shí)，推廣關(guān)鍵詞“培訓(xùn)”與“培訓(xùn)價(jià)格”或“seo培訓(xùn)”不匹配，僅在有人搜索“培訓(xùn)”時(shí)推廣信息才被觸發(fā)，這樣可以對(duì)展現(xiàn)條件進(jìn)行完全的控制。
優(yōu)勢(shì)：可獲得Z具針對(duì)性的點(diǎn)擊訪問(wèn)，轉(zhuǎn)化率較高。
劣勢(shì)：會(huì)降低創(chuàng)意的展示次數(shù)，獲得潛在客戶的范圍較窄。
否定匹配：與短語(yǔ)匹配和廣泛匹配相配合使用，對(duì)于一些可能被匹配但與推廣意圖不相符合的關(guān)鍵詞可以添加到否定匹配關(guān)鍵詞表中來(lái)阻止對(duì)應(yīng)推廣信息的觸發(fā)�？梢赃x擇其反面或非經(jīng)營(yíng)業(yè)務(wù)類的詞作為否定關(guān)鍵詞。
例如：商戶只做英語(yǔ)培訓(xùn)，不做日語(yǔ)培訓(xùn)，則可以選擇“日語(yǔ)”作為否定詞。商戶還可以在統(tǒng)計(jì)報(bào)告中的“搜索詞報(bào)告”中找出與業(yè)務(wù)無(wú)關(guān)的關(guān)鍵詞，將其設(shè)置為否定詞。
優(yōu)勢(shì)：使客戶在通過(guò)廣泛匹配和短語(yǔ)匹配獲得更多潛在用戶訪問(wèn)的同時(shí)，通過(guò)濾除不能為客戶帶去潛在客戶訪問(wèn)的不必要展現(xiàn)，降低轉(zhuǎn)化成本，提高投資回報(bào)率。
劣勢(shì)：設(shè)置否定關(guān)鍵詞后，將降低關(guān)鍵詞的展現(xiàn)概率，即獲得潛在客戶關(guān)注的概率降低。
每個(gè)關(guān)鍵詞的短語(yǔ)匹配和廣泛匹配都可以視為對(duì)一組詞的選定，并可以通過(guò)否定匹配進(jìn)行校正。合理的運(yùn)用關(guān)鍵詞的匹配，對(duì)于提高推廣效果，降低推廣成本起到很好的作用。
競(jìng)價(jià)匹配模式——馬海祥博客知識(shí)點(diǎn)擴(kuò)展
問(wèn)：廣泛匹配怎么用��？會(huì)不會(huì)讓我白花錢啊？
答：廣泛匹配是關(guān)鍵詞的一種匹配模式，它能夠Z大范圍的幫助您覆蓋潛在目標(biāo)客戶，讓您展現(xiàn)在更多潛在客戶面前。與此同時(shí)，您不必?fù)?dān)心因覆蓋范圍過(guò)大而產(chǎn)生缺乏針對(duì)性的訪問(wèn)，因?yàn)樗阉魍茝V提供了搜索詞統(tǒng)計(jì)報(bào)告和否定匹配的功能。
首先，您可以通過(guò)搜索詞統(tǒng)計(jì)報(bào)告查看網(wǎng)民是通過(guò)哪些搜索詞訪問(wèn)到自己的。將不適合展現(xiàn)您推廣結(jié)果的搜索詞，直接通過(guò)搜索推廣獨(dú)有的否定匹配功能，進(jìn)行排除即可。同時(shí)，進(jìn)一步洞悉哪些關(guān)鍵詞價(jià)值高，更符合網(wǎng)民的搜索習(xí)慣，從而，進(jìn)一步優(yōu)化和豐富您的推廣內(nèi)容。
通過(guò)將廣泛匹配、搜索詞統(tǒng)計(jì)報(bào)告和否定匹配三種功能的結(jié)合使用，循環(huán)優(yōu)化，一定能使您的推廣效果價(jià)值Z大化。這也正是搜索推廣功能所獨(dú)具的優(yōu)勢(shì)，讓您的推廣更科學(xué)更合理
問(wèn)：為什么搜索某個(gè)我沒(méi)提交的詞，我的關(guān)鍵詞也出現(xiàn)了？廣泛匹配默認(rèn)是什么都不加，而客戶提交關(guān)鍵詞的時(shí)候就是習(xí)慣什么都不加，你們就是利用這個(gè)來(lái)賺客戶不知情的錢。（為什么沒(méi)有人提醒我有廣泛匹配這個(gè)情況��？我多花了好多沒(méi)用的錢，你們?cè)趺唇忉專。?/SPAN>
答：廣泛匹配可以Z大范圍的覆蓋潛在目標(biāo)客戶，是一種既能高針對(duì)性投放，又能廣泛接觸受眾的方式。使用廣泛匹配可以增加您展現(xiàn)的機(jī)會(huì)，提升您的品牌知名度。在新建計(jì)劃、單元、撰寫(xiě)創(chuàng)意、提交關(guān)鍵詞的過(guò)程中，提交關(guān)鍵詞頁(yè)面的下方，對(duì)于各種匹配方式和設(shè)置方式都有明確提示的。
如果您覺(jué)得解釋的不夠詳盡，也可以馬海祥博客本文中上面介紹來(lái)了解各種匹配方式，以選擇Z適合的方式進(jìn)行推廣。
問(wèn)：如果我發(fā)現(xiàn)不相關(guān)的搜索詞展現(xiàn)了我的結(jié)果，怎么辦？
策略：黃金組合持續(xù)優(yōu)化。
答：廣泛匹配是關(guān)鍵詞的一種匹配模式，它能夠Z大范圍的幫助您覆蓋潛在目標(biāo)客戶，讓您展現(xiàn)在更多潛在客戶面前。與此同時(shí)，您不必?fù)?dān)心因覆蓋范圍過(guò)大而產(chǎn)生缺乏針對(duì)性的訪問(wèn)，因?yàn)樗阉魍茝V提供了搜索詞統(tǒng)計(jì)報(bào)告和否定匹配的功能。首先，您可以通過(guò)搜索詞統(tǒng)計(jì)報(bào)告查看網(wǎng)民是通過(guò)哪些搜索詞訪問(wèn)到自己的。將不適合展現(xiàn)您推廣結(jié)果的搜索詞，直接通過(guò)搜索推廣獨(dú)有的否定匹配功能，進(jìn)行排除即可。同時(shí)，進(jìn)一步洞悉哪些關(guān)鍵詞價(jià)值高，更符合網(wǎng)民的搜索習(xí)慣，從而，進(jìn)一步優(yōu)化和豐富您的推廣內(nèi)容。
通過(guò)將廣泛匹配、搜索詞統(tǒng)計(jì)報(bào)告和否定匹配三種功能的結(jié)合使用，持續(xù)優(yōu)化，一定能使您的推廣效果價(jià)值Z大化。這也正是搜索推廣功能所獨(dú)具的優(yōu)勢(shì)，讓您的推廣更科學(xué)更合理。
問(wèn)：現(xiàn)在都是廣泛匹配了，是不是就提核心詞就行了？
策略：詞少影響推廣效果，引導(dǎo)使用工具提詞；
答：關(guān)鍵詞參加廣泛匹配后，它能夠Z大范圍的幫助您覆蓋潛在目標(biāo)客戶，讓您展現(xiàn)在更多潛在客戶面前，但是如果只提交核心詞，縮小提詞范圍從整體推廣來(lái)看還是會(huì)影響您的覆蓋范圍和推廣效果。
所以建議，您可以通過(guò)搜索詞報(bào)告和關(guān)鍵詞推薦工具，查找提交具備商業(yè)性的關(guān)鍵詞，并參與廣泛匹配，會(huì)讓您的推廣結(jié)果獲得更多有針對(duì)性的關(guān)注，從而取得更好的推廣效果。
問(wèn)：否定關(guān)鍵詞怎么設(shè)置呢？怎么選擇合適的否定關(guān)鍵詞啊？
答：在選詞階段，您可根據(jù)企業(yè)的產(chǎn)品特性，排查出推薦工具所推薦的低質(zhì)詞匯，并將這些詞設(shè)置為否定關(guān)鍵詞就可以實(shí)現(xiàn)否定匹配了；您也可以通過(guò)搜索推廣新增的“搜索詞統(tǒng)計(jì)報(bào)告”，來(lái)排查那些不符合需求的詞，直接將其設(shè)置為否定關(guān)鍵詞即可。
在文本編輯中，我們經(jīng)常要在一段文本中某個(gè)特定的位置找出 某個(gè)特定的字符或模式。
由此，便產(chǎn)生了字符串的匹配問(wèn)題。
本文由簡(jiǎn)單的字符串匹配算法開(kāi)始，經(jīng)Rabin-Karp算法，Z后到KMP算法，教你從頭到尾解決理解KMP算法。
來(lái)看算法導(dǎo)論一書(shū)上關(guān)于此字符串問(wè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ù)上圖，再來(lái)解釋下字符串匹配問(wèn)題。目標(biāo)是找出所有在文本T=abcabaabcaabac中的模式P=abaa所有出現(xiàn)。
該模式僅在文本中出現(xiàn)了一次，在位移s=3處。位移s=3是有效位移。
一、簡(jiǎn)單的字符串匹配算法
簡(jiǎn)單的字符串匹配算法用一個(gè)循環(huán)來(lái)找出所有有效位移，
該循環(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次。
所以，在Z壞情況下，此簡(jiǎn)單模式匹配算法的運(yùn)行時(shí)間為O（(n-m+1)m）。
--------------------------------
下面我再來(lái)舉個(gè)具體例子，并給出一具體運(yùn)行程序：
對(duì)于目的字串target是banananobano,要匹配的字串pattern是nano,的情況，
下面是匹配過(guò)程，原理很簡(jiǎn)單，只要先和target字串的第一個(gè)字符比較，
如果相同就比較下一個(gè)，如果不同就把pattern右移一下，
之后再?gòu)膒attern的每一個(gè)字符比較，這個(gè)算法的運(yùn)行過(guò)程如下圖。
//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)一位，那么nanZ先匹配的字符序列將是an,這肯定是不能匹配的，
之后再右移一位，匹配的是nanZ先匹配的序列是n,這是可以匹配的。
如果我們事先知道pattern本身的這些信息就不用每次匹配失敗后都把target_index回退回去，
這種回退就浪費(fèi)了很多不必要的時(shí)間，如果能事先計(jì)算出pattern本身的這些性質(zhì)，
那么就可以在失配時(shí)直接把pattern移動(dòng)到下一個(gè)可能的位置，
把其中根本不可能匹配的過(guò)程省略掉，
如上表所示我們?cè)趇ndex=2時(shí)失配，此時(shí)就可以直接把pattern移動(dòng)到index=4的狀態(tài)，
kmp算法就是從此出發(fā)。
二、KMP算法
1、 覆蓋函數(shù)(overlay_function)
覆蓋函數(shù)所表征的是pattern本身的性質(zhì)，可以讓為其表征的是pattern從左開(kāi)始的所有連續(xù)子串的自我覆蓋程度。
比如如下的字串，abaabcaba
由于計(jì)數(shù)是從0始的，因此覆蓋函數(shù)的值為0說(shuō)明有1個(gè)匹配，對(duì)于從0還是從來(lái)開(kāi)始計(jì)數(shù)是偏好問(wèn)題，
具體請(qǐng)自行調(diào)整，其中-1表示沒(méi)有覆蓋，那么何為覆蓋呢，下面比較數(shù)學(xué)的來(lái)看一下定義，比如對(duì)于序列
a0a1...aj-1 aj
要找到一個(gè)k,使它滿足
a0a1...ak-1ak=aj-kaj-k+1...aj-1aj
而沒(méi)有更大的k滿足這個(gè)條件，就是說(shuō)要找到盡可能大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)過(guò)程.
下面給出一段計(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)匹配過(guò)的部分在pattern自身就能體現(xiàn)出來(lái)，只要?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算法的過(guò)程（紅色即是采用KMP算法的執(zhí)行過(guò)程）：
ok，Z后給出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算法的來(lái)源
kmp如此精巧，那么它是怎么來(lái)的呢，為什么要三個(gè)人合力才能想出來(lái)。其實(shí)就算沒(méi)有kmp算法，人們?cè)谧址ヅ渲幸材苷业较嗤咝У乃惴�。這種算法,Z終相當(dāng)于kmp算法，只是這種算法的出發(fā)點(diǎn)不是覆蓋函數(shù)，不是直接從匹配的內(nèi)在原理出發(fā)，而使用此方法的計(jì)算的覆蓋函數(shù)過(guò)程序復(fù)雜且不易被理解，但是一但找到這個(gè)覆蓋函數(shù)，那以后使用同一pattern匹配時(shí)的效率就和kmp一樣了，其實(shí)這種算法找到的函數(shù)不應(yīng)叫做覆蓋函數(shù)，因?yàn)樵趯ふ疫^(guò)程中根本沒(méi)有考慮是否覆蓋的問(wèn)題。
說(shuō)了這么半天那么這種方法是什么呢，這種方法是就大名鼎鼎的確定的有限自動(dòng)機(jī)(Deterministic finite state automaton DFA),DFA可識(shí)別的文法是3型文法，又叫正規(guī)文法或是正則文法，既然可以識(shí)別正則文法，那么識(shí)別確定的字串肯定不是問(wèn)題(確定字串是正則式的一個(gè)子集)。對(duì)于如何構(gòu)造DFA,是有一個(gè)完整的算法，這里不做介紹了。在識(shí)別確定的字串時(shí)使用DFA實(shí)在是大材小用，DFA可以識(shí)別更加通用的正則表達(dá)式，而用通用的構(gòu)建DFA的方法來(lái)識(shí)別確定的字串，那這個(gè)overhead就顯得太大了。
kmp算法的可貴之處是從字符匹配的問(wèn)題本身特點(diǎn)出發(fā)，巧妙使用覆蓋函數(shù)這一表征pattern自身特點(diǎn)的這一概念來(lái)快速直接生成識(shí)別字串的DFA,因此對(duì)于kmp這種算法，理解這種算法高中數(shù)學(xué)就可以了，但是如果想從無(wú)到有設(shè)計(jì)出這種算法是要求有比較深的數(shù)學(xué)功底的。
