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