我所理解的KMP算法
作者：goal00001111（高粱）
始發(fā)于goal00001111的專欄；允許自由轉(zhuǎn)載，但必須注明作者和出處
<!--[if !supportLists]-->一．<!--[endif]-->簡(jiǎn)單字符串模式匹配算法的缺陷
設(shè)有目標(biāo)串T(target)和模式串P(pattern)，模式匹配是指在目標(biāo)串T中找到一個(gè)與模式串P相等的子串。模式匹配成功是指在目標(biāo)串T中找到了一個(gè)模式串P。
簡(jiǎn)單字符串模式匹配算法（也就是BF算法）的基本思想是：從目標(biāo)串T的起始比較位置pos開(kāi)始（在后面的案例中，我們默認(rèn)pos = 0），和模式串P的第一個(gè)字符比較之，若匹配，則繼續(xù)逐個(gè)比較后繼字符，否則從串T的下一個(gè)字符起再重新和串P的字符比較之。依此類推，直至串P中的每個(gè)字符依次和串T中的一個(gè)連續(xù)的字符序列（即匹配子串）相等，則稱匹配成功，返回該匹配子串的首字符下標(biāo)；否則成匹配不成功，返回-1。
BF算法的思想很直接，也很容易理解，其時(shí)間復(fù)雜度為O（lenT*lenP），其中lenT和lenP分別為串T和串P的長(zhǎng)度。
我們先給出代碼，再做簡(jiǎn)要分析：
/*
函數(shù)名稱：BFIndex
函數(shù)功能：簡(jiǎn)單字符串模式匹配算法，若目標(biāo)串T中從下標(biāo)pos起存在和模式串P相同的子串，則稱匹配成功，返回第一個(gè)匹配子串首字符的下標(biāo)；否則返回-1。
輸入?yún)?shù)：const string & T ：目標(biāo)串T
const string & P ：模式串P
int pos ：模式匹配起始位置
輸出參數(shù)：int ：匹配成功，返回第一個(gè)匹配子串首字符的下標(biāo)；否則返回-1。
*/
int BFIndex(const string & T, const string & P, int pos)
{
int i = pos;
int j = 0;
while (i < T.size() && j < P.size())
{
if (T[i] == P[j]) //如果當(dāng)前字符匹配，繼續(xù)比較后繼字符
{
++i;
++j;
}
else //否則i，j回溯，重新開(kāi)始新的一輪比較
{
i = i - j + 1;
j = 0;
//if (i > T.size() - P.size()) //一旦目標(biāo)串剩余部分子串比模式串短，則無(wú)需再比較
// break;
}
}
if (j == P.size()) //匹配成功，返回第一個(gè)匹配子串首字符的下標(biāo)
return i - j;
else
return -1;
}
我們發(fā)現(xiàn)，在某一輪比較中，一旦出現(xiàn)字符失配（即T[i] != P[j]），則需將i和j回溯，其中i回溯至i = i - j + 1，j回溯至j = 0。
這樣產(chǎn)生了很多不必要的比較，例如（例1）：
string T = "aababaabaabc";
string P = "abaabc";
在第4輪比較中，T3T4T5T6T7 == P0P1P2P3P4，我將其簡(jiǎn)寫(xiě)為T[3…7] == P[0…4]（后面的都這樣表示），但T[8] != P[5]，出現(xiàn)字符失配，需要將i和j回溯，使得i = 4， j = 0。
而在第4輪比較中，我們已經(jīng)得到了T[6…7] == P[3…4]，又P[0…1] == P[3…4]，相當(dāng)于T[6…7]和P[0…1]已經(jīng)間接地比較過(guò)，而且字符匹配了，我們無(wú)需進(jìn)行從i =6， j = 0開(kāi)始的重復(fù)比較。
實(shí)際上，當(dāng)T[8] != P[5]，即在i = 8， j = 5處出現(xiàn)字符失配時(shí)，我們無(wú)需將i回溯，只需將j回溯至failure[j]（此時(shí)failure[5] = 2）處即可。即當(dāng)T[8] != P[5]時(shí)，我們可以跳過(guò)比較T[6…7]和P[0…1]（因?yàn)樗鼈円呀?jīng)間接地比較過(guò)了），直接比較字符T[8]和P[2]，這樣可以省去很多不必要的回溯和比較，時(shí)間復(fù)雜度達(dá)到O（lenT+lenP）。這就是KMP算法的核心思想。
二．高效的KMP算法
現(xiàn)在繼續(xù)剖析KMP算法。
我在上文提到當(dāng)T[i] != P[j]時(shí)，我們無(wú)需將i回溯，只需將j回溯至failure[j]處即可。我們稱failure[j]為模式串P下標(biāo)j的失效函數(shù)。
失效函數(shù)的值failure[j]是指當(dāng)T[i] != P[j]時(shí)，接下來(lái)與T[i]進(jìn)行比較的模式串P的元素下標(biāo)。如上面的例子，當(dāng)T[8] != P[5]時(shí)，因?yàn)?/span>T[6…7] == P[3…4] == P[0…1]，我們可以跳過(guò)比較T[6…7]和P[0…1]，直接比較字符T[8]和P[2]，所以failure[5] = 2。
如果你對(duì)失效函數(shù)還不太理解，我再舉一些例子。
仍然以上面提供的目標(biāo)串T和模式串S為例，當(dāng)出現(xiàn)T[1…3] == P[0…2]，但T[4] != P[3]時(shí)，若采用BF算法，則需要將i和j回溯，使得i = 2， j = 0。
而采用KMP算法，則無(wú)需將i回溯，j也不需要回溯至j = 0，而只需回溯至j = failure[j]。那如何得知failure[j]的值呢？觀察模式串P，我們發(fā)現(xiàn)P[2] == P[0]，因?yàn)?/span>T[3] == P[2]，所以T[3] == P[0]，相當(dāng)于我們已經(jīng)間接地比較過(guò)T[3] 和P[0]了，無(wú)需重復(fù)比較，接下來(lái)可以直接比較T[4]和P[1]，所以failure[3] = 1。
再看一個(gè)簡(jiǎn)單的例子（例2）：
string T = "aabcabaababc";
string P = "ababc";
當(dāng)出現(xiàn)T[0] == P[0]，但T[1] != P[1]時(shí)，要保證i不變，必須將j回溯至j = 0，然后比較T[1] 和P[0]，所以failure[1] = 0。
同樣的，當(dāng)出現(xiàn)T[4…6] == P[0…2]，但T[7] != P[3]時(shí)，要保證i不變，必須將j回溯至j = 0（為什么？好好想想?。?，然后比較T[7] 和P[0]，所以failure[3] = 0。
那么，如果模式串P的第一個(gè)元素就不匹配，即T[i] != P[0]又該怎么辦呢？j已經(jīng)最小，沒(méi)辦法再往前回溯了，下一次比較必須使i自增1。這是一種特殊的情況，考慮到C語(yǔ)言中的數(shù)組下標(biāo)從0開(kāi)始，為了表示區(qū)別，我們?cè)O(shè)failure[0] = -1。很明顯當(dāng)failure[j] != -1時(shí)，在進(jìn)行下一次比較之前，我們無(wú)需改變i的值；而當(dāng)failure[j] == -1時(shí)，在進(jìn)行下一次比較之前，必須先使i自增1。
我們繼續(xù)分析例2，當(dāng)出現(xiàn)T[1…2] == P[0…1]，但T[3] != P[2]時(shí)，要保證i不變，必須將j回溯至j = 0，然后比較T[3] 和P[0]——看上去好像一切都順理成章，但是請(qǐng)等等！ 經(jīng)比較T[3] != P[2]，經(jīng)觀察P[2] == P[0]，我們還有必要再去比較T[3] 和P[0]嗎？當(dāng)然不需要，我們應(yīng)該直接比較T[4] 和P[0]才對(duì)！所以failure[2] = -1。
舉了一大堆例子，苦于沒(méi)有圖象對(duì)照，想必各位看官已經(jīng)看得頭都大了！到底如何求模式串P的失效函數(shù)failure[j]，可能很多人還是一頭霧水（PS：我計(jì)劃做一個(gè)教學(xué)視頻，到時(shí)候圖文聲并茂，一定會(huì)幫助你理解的，記得隨時(shí)關(guān)注博客，等待觀看哦）。據(jù)考證，失效函數(shù)failure[j]是模式串P本身的屬性，與目標(biāo)串T無(wú)關(guān)，而且從不同的角度分析模式串P可以得到失效函數(shù)的不同表示方法。網(wǎng)絡(luò)上此類文章可謂汗牛充棟，我的關(guān)于失效函數(shù)failure[j]的理解，與網(wǎng)友A_B_C_ABC 在其博文《KMP字符串模式匹配詳解》（http://blog.csdn.net/A_B_C_ABC/archive/2005/11/25/536925.aspx）中所論述的“第一種表示方法”極為相似，如果你不想讀我的文字，可以先去看A_B_C_ABC貼的圖片，回過(guò)頭再看我的文章，也許會(huì)明白我的意思——不會(huì)作圖的下場(chǎng)??！555
現(xiàn)在去A_B_C_ABC的博客看圖！
。。。。。。
現(xiàn)在明白失效函數(shù)failure[j]的意義了吧？也應(yīng)該知道如何求解failure[j]了吧？
總結(jié)一下吧：
先看失效函數(shù)的意義。
設(shè)在目標(biāo)串T中查找模式串P，若T[i] != P[j]，則將j回溯至失效函數(shù)值failure[j]處，那failure[j]可以取到哪些值呢？
① failure[0]= -1，表示T[i]和P[0]間接比較過(guò)了，且T[i] != P[0]，接下來(lái)比較T[i+1]和P[0]；
② failure[j] = 0，表示比較過(guò)程中產(chǎn)生了不相等，接下來(lái)比較T[i]和P[0]；
③ failure[j] = k，其中0 < k < j，表示T[i]之前的k個(gè)字符與P中的前k個(gè)字符已經(jīng)間接比較過(guò)了，且P[0…k-1] == P[j-k…j-1] == T[i-k…i-1]，接下來(lái)比較T[i]和P[k]。
除了上述三種情況，failure[j]不可能取到其他值。
那么如何求解失效函數(shù)failure[j]的值呢？
從上述討論可見(jiàn)，失效函數(shù)failure[j]的值僅取決于模式串P本身，與目標(biāo)串T無(wú)關(guān)。
① failure[0]= -1：考慮到C語(yǔ)言中的數(shù)組下標(biāo)從0開(kāi)始，模式串P的首字符的失效函數(shù)值規(guī)定為-1；
② failure[j] = -1：若P[j] == P[0]，且P[0…k-1] != P[j-k…j-1]，或P[0…k] == P[j-k…j]，其中0 < k < j。
如：P = "abcaabcab"。
因?yàn)?/span>P[3] == P[0]，且P[0] != P[2]，P[0…1] != P[2…3]，則failure[3] = -1；
又因?yàn)?/span>P[7] == P[0]，且P[0…3] == P[4…7]，則failure[7] = -1；
③ failure[j] = k：若P[0…k-1] == P[j-k…j-1]，且P[k] != P[j]，其中0 < k < j。
如：P = "abcaabcab"。
因?yàn)?/span>P[0] == P[3]，且P[1] != P[4]，則failure[4] = 1；
又因?yàn)?/span>P[0…3] == P[4…7]，且P[4] != P[8]，則failure[8] = 4；
④ failure[j] = 0：除（1）（2）（3）的其他情況。
如：P = "abcaabcab"中，failure[1] = failure[2] = failure[5] = failure[6] = 0；
算法思路：
KMPIndex函數(shù)：
KMP算法在形式上和BF算法即為相似。不同之處僅在于：當(dāng)匹配過(guò)程中產(chǎn)生“失配”時(shí)，目標(biāo)串T指示標(biāo)志i不變，模式串P指示標(biāo)志j回溯至failure[j]所指示的位置，并且當(dāng)j回溯至最左端（即failure[j] == -1）時(shí)，使j = 0，i自增1，。
GetFailure函數(shù)：
根據(jù)failure[j]的定義，我們先規(guī)定failure[0] = -1；然后遍歷模式串P，依次計(jì)算各個(gè)元素的失配函數(shù)值。
設(shè)已有k == 0；或0 < k < j，且P[0…k-1] == P[j-k…j-1]；我們比較P[k]和 P[j]：
若P[k] == P[j]，則由failure[j]的定義可知failure[j] = failure[k]，之后k和j均自增1，繼續(xù)比較后繼字符；
若P[k] != P[j]，則failure[j] = k。很明顯之后不能直接比較后繼字符；而需要將k回溯，直至找到使得P[0…k] == P[j-k…j]的最大k值，才可以讓k和j均自增1，繼續(xù)比較后繼字符。
那么如何將k快速回溯到適當(dāng)?shù)奈恢媚兀?/span>
我們?cè)O(shè)h = failure[k]，很明顯有：P[0…h-1] == P[k-h…k-1] == P[j-h…j-1]。
若P[h] == P[j]，那h就是滿足條件的最大k值。
若P[h] != P[j]，則再在串P[0…h]中尋找更小的failure[h]。如此遞推，有可能還需要以同樣的方式再縮小尋找范圍，直到failure[h] == -1才算失敗。
若failure[h] == -1，則相當(dāng)于k已經(jīng)回溯到了模式串P的最左端，可以讓k和j均自增1，繼續(xù)比較后繼字符。
實(shí)現(xiàn)代碼如下：
/*
函數(shù)名稱：KMPIndex
函數(shù)功能：Knuth－Morris－Pratt算法，若目標(biāo)串T中從下標(biāo)pos起存在和模式串P相同的子串，則稱匹配成功，返回第一個(gè)匹配子串首字符的下標(biāo)；否則返回-1。
輸入?yún)?shù)：const string & T ：目標(biāo)串T
const string & P ：模式串P
int pos ：模式匹配起始位置
輸出參數(shù)：無(wú)
返回值：int ：匹配成功，返回第一個(gè)匹配子串首字符的下標(biāo)；否則返回-1。
*/
int KMPIndex(const string & T, const string & P, int pos)
{
int *failure = new int[P.size()];
Getfailure(P, failure); //計(jì)算模式串P的失配函數(shù)failure[]
int i = pos;
int j = 0;
while (i < T.size() && j < P.size())
{
if (T[i] == P[j]) //如果當(dāng)前字符匹配，繼續(xù)比較后繼字符
{
++i;
++j;
}
else //否則保持i不變，將j回溯至failure[j]，開(kāi)始新的一輪比較
{
j = failure[j];
if (j == -1) //若j回溯至最左端，則使j = 0，i自增1
{
j = 0;
++i;
}
}
}
delete []failure;
if (j == P.size()) //匹配成功，返回第一個(gè)匹配子串首字符的下標(biāo)
return i - j;
else
return -1;
}
/*
函數(shù)名稱：Getfailure
函數(shù)功能：計(jì)算模式串P的失配函數(shù)，并存入數(shù)組failure[]
輸入?yún)?shù)：const string & P ：模式串P
int failure[]：模式串P的失配函數(shù)
輸出參數(shù)：int failure[]：模式串P的失配函數(shù)
返回值：無(wú)
*/
void Getfailure(const string & P, int failure[])
{
failure[0] = -1; //模式串P的首字符的失配函數(shù)值規(guī)定為-1
for (int j=1, k=0; j<P.size(); j++, k++)//遍歷模式串P，計(jì)算失配函數(shù)值
{
//若P[0…k-1] == P[j-k…j-1]，且P[k] == P[j]，則failure[j] = failure[k]，并繼續(xù)比較后繼字符
if (P[k] == P[j])
{
failure[j] = failure[k];
}
else //否則保持j不變，將k回溯至failure[k]
{
failure[j] = k; //若P[0…k-1] == P[j-k…j-1]，且P[k] != P[j]，則failure[j] = k
//尋找使得P[0…k] == P[j-k…j]的最大k值，才可以繼續(xù)比較后繼字符
while (k >= 0 && P[k] != P[j])//將k回溯至P[k] == P[j]或最左端，以進(jìn)行下一輪比較
k = failure[k];
}
}
//以下代碼輸出failure[i]
for (int i=0; i<P.size(); i++)
cout << failure[i] << " ";
cout << endl;
}
我們剛才討論的失效函數(shù)中有一個(gè)很巧妙的地方，那就是除了failure[0] = -1以外，模式串P中還有多處failure[j]可以等于-1，這就避免了重復(fù)比較T[i]和P[0]，可以直接比較T[i+1]和P[0]。但是最初接觸到這個(gè)算法的時(shí)候，我被這個(gè)“巧妙之處”足足折騰了半天——只因?yàn)樾噬系囊稽c(diǎn)點(diǎn)提高，卻帶來(lái)了理解上的巨大困難——真是得不償失?。?/span>
那么有沒(méi)有更好理解的失效函數(shù)呢？當(dāng)然有！
三．更好理解的失效函數(shù)
接下來(lái)我們看看另一些常見(jiàn)的失效函數(shù)表示方法。
在嚴(yán)蔚敏和吳偉民編著的《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》（清華大學(xué)出版社）一書(shū)中，采用了一種比較簡(jiǎn)單的失效函數(shù)表示方法。它的定義與前面講的失效函數(shù)差不多，只是把上述的四種情況簡(jiǎn)化為三種情況，將②和③合并為同一種類型，即若P[0…k-1] == P[j-k…j-1]，其中0 < k < j，則failure[j] = k，而不論P[k] 是否等于 P[j]。這樣模式串P中就只有failure[0] = -1了，失效函數(shù)表示方法得到了簡(jiǎn)化——當(dāng)然效率稍微有所降低。
采用這種失效函數(shù)表示方法，在求解失效函數(shù)時(shí)，可以利用簡(jiǎn)單的遞推，根據(jù)failure[j]來(lái)得到failure[j+1]。
原理如下：
先給出兩個(gè)概念：若存在0 <= k < j，且使得P[0…k] == P[j-k…j]的最大整數(shù)k，我們稱P[0…k]為串P[0…j]的前綴子串，P[j-k…j]為串P[0…j]的后綴子串。
從failure[j]的定義出發(fā)，計(jì)算failure[j]就是要在串P[0…j]中找出最長(zhǎng)的相等的前綴子串P[0…k]和后綴子串P[j-k…j]，這個(gè)查找的過(guò)程實(shí)際上仍是一個(gè)模式匹配的過(guò)程，只是目標(biāo)和模式現(xiàn)在是同一個(gè)串P。
我們可以用遞推的方法求failure[j]的值。
設(shè)已有failure[j] = k，則有0 < k < j，且P[0…k-1] == P[j-k…j-1]。接下來(lái)：
若P[k] == P[j]，則由failure[j]的定義可知failure[j+1] = k + 1 = failure[j] + 1；
若P[k] != P[j]，則可以在前綴子串P[0…k]中尋找使得P[0…h-1] == P[k-h…k-1]的h，這時(shí)存在兩種情況：
① 找到h，則由failure[j]的定義可知failure[k] = h，故P[0…h-1] == P[k-h…k-1] == P[j-h…j-1]，即在串P[0…j]中找到了長(zhǎng)度為h的相等的前綴子串和后綴子串。
這時(shí)若P[h] == P[j]，則由failure[j]的定義可知failure[j+1] = h + 1 = failure[k] + 1 = failure[failure[j]] + 1；
若P[h] != P[j]，則再在串P[0…h]中尋找更小的failure[h]。如此遞推，有可能還需要以同樣的方式再縮小尋找范圍，直到failure[h] == -1才算失敗。
② 找不到h，這時(shí)failure[k] == -1，即k已經(jīng)回溯到k = failure[k] = -1，所以failure[j+1] = k + 1 = 0。
依據(jù)以上分析，仿照KMP算法，可以得到計(jì)算failure[j]的算法，其對(duì)應(yīng)的KMPIndex函數(shù)不變。
代碼如下：
/*
函數(shù)名稱：Getfailure
函數(shù)功能：用遞推的方法計(jì)算模式串P的失配函數(shù)，并存入數(shù)組failure[]
輸入?yún)?shù)：const string & P ：模式串P
int failure[]：模式串P的失配函數(shù)
輸出參數(shù)：int failure[]：模式串P的失配函數(shù)
返回值：無(wú)
*/
void Getfailure(const string & P, int failure[])
{
failure[0] = -1; //模式串P的首字符的失配函數(shù)值規(guī)定為-1
for (int j=1; j<P.size(); j++)//遍歷模式串P，計(jì)算失配函數(shù)值
{
int k = failure[j-1]; //利用failure[j-1]遞推failure[j]，k指向failure[j-1]
while (k >= 0 && P[k] != P[j-1])//將k回溯至P[k] == P[j-1]或k == -1，以進(jìn)行下一輪比較
k = failure[k];
//現(xiàn)在可以確保P[0…k] == P[j-k-1…j-1]，則failure[j] = k + 1（若k == -1，則failure[j] = 0）
failure[j] = k + 1;
}
//以下代碼輸出failure[i]
for (int i=0; i<P.size(); i++)
cout << failure[i] << " ";
cout << endl;
}
前面定義的失效函數(shù)在某些情況下尚有缺陷。例如當(dāng)模式串P = "aaaaaaaaaab"時(shí)，若T[i] != P[9]，因?yàn)?/span>failure[9] = 8，所以下一步要將T[i] 和 P[8]比較；依此類推還要比較P[7]，P[6]，。。。，P[0]。實(shí)際上，因?yàn)樗鼈兌枷嗟?，所以?dāng)T[i] != P[9]時(shí)，可以直接比較T[i] 和 P[0]。也就是說(shuō)，若按上述定義得到failure[j] = k，且P[j] == P[k]時(shí)，則當(dāng)T[i] != P[j]時(shí)，不需要再比較T[i] 和 P[k]，可以直接比較T[i] 和 P[failure[k]]，即此時(shí)的failure[j]應(yīng)該等于failure[k]。由此我們可以在原來(lái)計(jì)算失效函數(shù)算法的基礎(chǔ)上加上一條語(yǔ)句，對(duì)失效函數(shù)值進(jìn)行修正，以得到更高效的KMP算法。而且我們可以檢驗(yàn)修正后的失效函數(shù)值與用第一種方法得到的失效函數(shù)值是一樣的。
計(jì)算失效函數(shù)修正值的代碼如下：
void Getfailure2(const string & P, int failure[])
{
failure[0] = -1; //模式串P的首字符的失效函數(shù)值規(guī)定為-1
for (int j=1; j<P.size(); j++)//遍歷模式串P，計(jì)算失效函數(shù)值
{
int k = failure[j-1]; //利用failure[j-1]遞推failure[j]，k指向failure[j-1]
while (k >= 0 && P[k] != P[j-1])//將k回溯至P[k] == P[j-1]或k == -1，以進(jìn)行下一輪比較
k = failure[k];
//現(xiàn)在可以確保P[0…k] == P[j-k-1…j-1]，則failure[j] = k + 1（若k == -1，則failure[j] = 0）
failure[j] = k + 1;
}
//對(duì)失效函數(shù)值進(jìn)行修正，可以得到更高效的KMP算法
for (int j=1; j<P.size(); j++)
{
if (P[j] == P[failure[j]])
failure[j] = failure[failure[j]];
}
//以下代碼輸出failure[i]
for (int i=0; i<P.size(); i++)
cout << failure[i] << " ";
cout << endl;
}
四．另類的KMP算法
在殷人昆等人編著的《數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述）》（清華大學(xué)出版社）一書(shū)中，用到了另外一種表示失效函數(shù)的方法。該方法與前述兩種方法的區(qū)別在于，當(dāng)T[i] != P[j]時(shí)，模式串P的下標(biāo)j不是回溯至failure[j]，而是回溯至failure[j-1]+1，所以它的KMPIndex函數(shù)和GetFailure函數(shù)都與前面的有所不同。
該書(shū)對(duì)失效函數(shù)failure[j]的定義如下：
① failure[j] = k，其中0 <= k < j，且使得P[0…k] == P[j-k…j]的最大整數(shù)；
② failure[j] = -1，其他情況。
如：P = "abcaabcab"。
j = 0時(shí)，沒(méi)有滿足0 <= k < j的k存在，故failure[0] = -1；
j = 1時(shí)，可取k = 0，但P[0] != P[1]，k不符合要求，故failure[1] = -1；
j = 2時(shí)，可取k = 0或1，但P[0] != P[2]，且P[0…1] != P[1…2]，k不符合要求，故failure[2] = -1；
j = 3時(shí)，可取k = 0，1或2：P[0] == P[3]，P[0…1] != P[2…3]，P[0…2] != P[1…3]，故failure[3] = k = 0；
j = 4時(shí)，可取k = 0，1，2或3：P[0] == P[4]，P[0…1] != P[3…4]，P[0…2] != P[2…4]，P[0…3] != P[1…4]，故failure[4] = k = 0；
j = 5時(shí)，可取k = 0。。4：P[0] != P[5]，P[0…1] == P[4…5]，P[0…2] != P[3…5]，P[0…3] != P[2…5]，P[0…4] != P[1…5]，故failure[5] = k = 1；
其他的以此類推可以得到failure[6] = 2；failure[7] = 3；failure[8] = 1。
設(shè)若在進(jìn)行某一趟匹配比較時(shí)在模式串P的j位失配，即T[i] != P[j]，如果j > 0，因?yàn)?/span>P[failure[j-1]] == P[j-1] == T[i-1]，即已經(jīng)間接地知道了P[0…failure[j-1]]是匹配的，那么我們只需將串P的下標(biāo)j回溯至failure[j-1]+1，串T的下標(biāo)i不回溯，仍指向上一趟失配的字符；如果j == 0，則讓串T的下標(biāo)i前進(jìn)一位，串P的起始比較位置回溯到P[0]，繼續(xù)做匹配比較。
如何正確地計(jì)算出失效函數(shù)failure[j]，是實(shí)現(xiàn)KMP算法的關(guān)鍵。
從failure[j]的定義出發(fā)，計(jì)算failure[j]就是要在串P[0…j]中找出最長(zhǎng)的相等的前綴子串P[0…k]和后綴子串P[j-k…j]，這個(gè)查找的過(guò)程實(shí)際上仍是一個(gè)模式匹配的過(guò)程，只是目標(biāo)和模式現(xiàn)在是同一個(gè)串P。
我們可以用遞推的方法求failure[j]的值（此方法與上文介紹的嚴(yán)蔚敏教授書(shū)中的方法極為相似，只有一處不同，請(qǐng)注意區(qū)別）。
設(shè)已有failure[j] = k，則有0 <= k < j，且P[0…k] == P[j-k…j]。
若P[k+1] == P[j+1]，則由failure[j]的定義可知failure[j+1] = k + 1 = failure[j] + 1；
若P[k+1] != P[j+1]，則可以在前綴子串P[0…k]中尋找使得P[0…h] == P[k-h…k]的h，這時(shí)存在兩種情況：
① 找到h，則由failure[j]的定義可知failure[k] = h，故P[0…h] == P[k-h…k] == P[j-h…j]，即在串P[0…j]中找到了長(zhǎng)度為h + 1的相等的前綴子串和后綴子串。
這時(shí)若P[h+1] == P[j+1]，則由failure[j]的定義可知failure[j+1] = h + 1 = failure[k] + 1 = failure[failure[j]] + 1；
若P[h+1] != P[j+1]，則再在串P[0…h]中尋找更小的failure[h]。如此遞推，有可能還需要以同樣的方式再縮小尋找范圍，直到failure[h] == -1才算失敗。
② 找不到h，這時(shí)failure[k] == -1。
依據(jù)以上分析，仿照KMP算法，可以得到計(jì)算failure[j]的算法。
/*
函數(shù)名稱：KMPIndex
函數(shù)功能：Knuth－Morris－Pratt算法，若目標(biāo)串T中從下標(biāo)pos起存在和模式串P相同的子串，
則稱匹配成功，返回第一個(gè)匹配子串首字符的下標(biāo)；否則返回-1。
輸入?yún)?shù)：const string & T ：目標(biāo)串T
const string & P ：模式串P
int pos ：模式匹配起始位置
輸出參數(shù)：無(wú)
返回值：int ：匹配成功，返回第一個(gè)匹配子串首字符的下標(biāo)；否則返回-1。
*/
int KMPIndex(const string & T, const string & P, int pos)
{
int *failure = new int[P.size()];
Getfailure(P, failure); //計(jì)算模式串P的失配函數(shù)failure[]
int i = pos;
int j = 0;
while (i < T.size() && j < P.size())
{
if (T[i] == P[j]) //如果當(dāng)前字符匹配，繼續(xù)比較后繼字符
{
++i;
++j;
}
else if (j == 0) //如果j == 0，則讓目標(biāo)串T的下標(biāo)i前進(jìn)一位
++i;
else //否則下一趟比較時(shí)模式串P的起始比較位置是P[failure[j-1]+1]，目標(biāo)串T的下標(biāo)i不回溯
j = failure[j-1] + 1;
}
delete []failure;
if (j == P.size()) //匹配成功，返回第一個(gè)匹配子串首字符的下標(biāo)
return i - j;
else
return -1;
}
/*
函數(shù)名稱：Getfailure
函數(shù)功能：用遞推的方法計(jì)算模式串P的失配函數(shù)，并存入數(shù)組failure[]
輸入?yún)?shù)：const string & P ：模式串P
int failure[]：模式串P的失配函數(shù)
輸出參數(shù)：int failure[]：模式串P的失配函數(shù)
返回值：無(wú)
*/
void Getfailure(const string & P, int failure[])
{
failure[0] = -1; //模式串P的首字符的失配函數(shù)值規(guī)定為-1
for (int j=1; j<P.size(); j++)//遍歷模式串P，計(jì)算失配函數(shù)值
{
int k = failure[j-1]; //利用failure[j-1]遞推failure[j]，k指向failure[j-1]
while (k >= 0 && P[k+1] != P[j])//將k回溯至P[k+1] == P[j]或k == -1，以進(jìn)行下一輪比較
k = failure[k];
if (P[k+1] == P[j]) //若P[0…k] == P[j-k…j-1]，且P[k+1] == P[j]，則failure[j] = k + 1
failure[j] = k + 1;
else //沒(méi)有找到滿足條件的k
failure[j] = -1;
}
//以下代碼輸出failure[i]
for (int i=0; i<P.size(); i++)
cout << failure[i] << " ";
cout << endl;
}
這樣我們就學(xué)習(xí)了三種失效函數(shù)的表示方法，雖然它們對(duì)應(yīng)的KMP算法代碼略有不同，但其本質(zhì)是一樣的，就是避免回溯目標(biāo)串T的下標(biāo)i，并使得模式串P的下標(biāo)j回溯到正確位置。同樣的，不管你用什么代碼來(lái)實(shí)現(xiàn)求解失效函數(shù)的算法，其本質(zhì)都是模式串內(nèi)部的模式匹配，采用遞推的方式，尋找最大的相同子串。
參考文獻(xiàn)：
1.《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》（清華大學(xué)出版社）嚴(yán)蔚敏，吳偉民編著
2.《數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述）》（清華大學(xué)出版社）殷人昆等人編著
3.《KMP字符串模式匹配詳解》來(lái)自網(wǎng)友A_B_C_ABC的博客
（http://blog.csdn.net/A_B_C_ABC/archive/2005/11/25/536925.aspx）
4.《KMP算法中Next[]數(shù)組求法》作者：劍心通明
（http://www.bsdlover.cn/html/21/n-3021.html）