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