參考文章
知乎：如何更好的理解和掌握 KMP 算法?
從頭到尾徹底理解KMP
KMP 算法（1）：如何理解 KMP
（原創(chuàng)）詳解KMP算法
字符串匹配——BMH算法
1. 引言
真的是遇事不決問知乎啊，知乎上對(duì)于KMP的理解提供了很多文章，July這篇文章比較通俗易懂，需要的可以去看原文，我想按照原文的邏輯順序梳理一下我原來不懂的地方。
2. 暴力匹配算法
簡單來說就是一個(gè)個(gè)字的比較，讓誰來寫都是這個(gè)樣。重點(diǎn)是這句話
- 如果當(dāng)前字符匹配成功（即S[i] == P[j]），則i++，j++，繼續(xù)匹配下一個(gè)字符
- 如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相當(dāng)于每次匹配失敗時(shí)，i 回溯，j 被置為0。
這就相當(dāng)于說要回溯m次，每次最多比較n回，時(shí)間復(fù)雜度就是O(mn),KMP就是通過少回溯來使得時(shí)間復(fù)雜度變?yōu)镺(m+n)。
3. KMP算法
3.1 定義
一個(gè)基本事實(shí)是，當(dāng)空格與 D 不匹配時(shí)，你其實(shí)是已經(jīng)知道前面六個(gè)字符是 "ABCDAB"。KMP 算法的想法是，設(shè)法利用這個(gè)已知信息，不要把 "搜索位置" 移回已經(jīng)比較過的位置，而是繼續(xù)把它向后移，這樣就提高了效率。
3.2 步驟
next數(shù)組的其實(shí)就是在 前綴后綴最長公共元素的基礎(chǔ)上得出來的，這個(gè)數(shù)組代表了當(dāng)這一位失配后，模式串的指針應(yīng)該調(diào)到哪一位（即next[i]中的值），當(dāng)這個(gè)值是-1的時(shí)候，表示目標(biāo)串指針要向后移動(dòng)，模式串的指針回溯到0。
3.3 通過代碼遞推計(jì)算next 數(shù)組
void GetNext(char* p,int next[])
{
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{
//p[k]表示前綴，p[j]表示后綴
if (k == -1 || p[j] == p[k])
{
++k;
++j;
next[j] = k;
}
else
{
k = next[k];
}
}
}
問題的關(guān)鍵應(yīng)該是如何用代碼求得next數(shù)組，顯然這里用到了類似于統(tǒng)計(jì)歸納法的證明方法，f(n)可以通過f(n-1)推導(dǎo)出來，關(guān)鍵是這句話
- 若p[i] == p[j]，則next[i + 1] = next [i] + 1 = j + 1；
- 若p[i] ≠ p[j]，如果此時(shí)p[ next[j] ] == p[i]，則next[ i + 1 ] = next[j] + 1，否則繼續(xù)遞歸前綴索引 j = next[j]，而后重復(fù)此過程。
這里還是拿圖比較明白
next[i] = j得，也就是對(duì)于位置 i 來說，區(qū)段 [0, i - 1] 的最長相同真前后綴分別是 [0, j - 1] 和[i - j, i - 1]，即這兩區(qū)段內(nèi)容相同。按照算法流程，if (P[i] == P[j])，則i++; j++; next[i] = j；相當(dāng)于得到了next[i+1]的值。
若不等，則j = next[j]，見下圖1/2/3：
4. KMP算法的優(yōu)化
這部分優(yōu)化優(yōu)化的是p[j] = p[ next[j] ]的問題。當(dāng)p[j] != s[i] 時(shí)，下次匹配必然是p[ next [j]] 跟s[i]匹配，如果p[j] = p[ next[j] ]，必然導(dǎo)致后一步匹配失敗。如果出現(xiàn)了p[j] = p[ next[j] ]則需要再次遞歸，即令next[j] = next[ next[j] ]，從而得到了完整的KMP算法。
//優(yōu)化過后的next 數(shù)組求法
void GetNextval(char* p, int next[])
{
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{
//p[k]表示前綴，p[j]表示后綴
if (k == -1 || p[j] == p[k])
{
++j;
++k;
//較之前next數(shù)組求法，改動(dòng)在下面4行
if (p[j] != p[k])
next[j] = k; //之前只有這一行
else
//因?yàn)椴荒艹霈F(xiàn)p[j] = p[ next[j ]]，所以當(dāng)出現(xiàn)時(shí)需要繼續(xù)遞歸，k = next[k] = next[next[k]]
next[j] = next[k];
}
else
{
k = next[k];
}
}
}
5. BM算法
KMP的匹配是從模式串的開頭開始匹配的，而1977年，德克薩斯大學(xué)的Robert S. Boyer教授和J Strother Moore教授發(fā)明了一種新的字符串匹配算法：Boyer-Moore算法，簡稱BM算法。該算法從模式串的尾部開始匹配，且擁有在最壞情況下O(N)的時(shí)間復(fù)雜度。在實(shí)踐中，BM算法不僅效率高，而且構(gòu)思巧妙，容易理解。
BM算法定義了兩個(gè)規(guī)則：
壞字符規(guī)則：當(dāng)文本串中的某個(gè)字符跟模式串的某個(gè)字符不匹配時(shí)，我們稱文本串中的這個(gè)失配字符為壞字符，此時(shí)模式串需要向右移動(dòng)，移動(dòng)的位數(shù) = 壞字符在模式串中的位置 - 壞字符在模式串中最右出現(xiàn)的位置。此外，如果"壞字符"不包含在模式串之中，則最右出現(xiàn)位置為-1。
好后綴規(guī)則：當(dāng)字符失配時(shí)，后移位數(shù) = 好后綴在模式串中的位置 - 好后綴在模式串上一次出現(xiàn)的位置，且如果好后綴在模式串中沒有再次出現(xiàn)，則為-1。
每次后移這兩個(gè)規(guī)則之中的較大值。這兩個(gè)規(guī)則的移動(dòng)位數(shù)，只與模式串有關(guān)，與原文本串無關(guān)。
下面舉例說明BM算法。例如，給定文本串“HERE IS A SIMPLE EXAMPLE”，和模式串“EXAMPLE”，現(xiàn)要查找模式串是否在文本串中，如果存在，返回模式串在文本串中的位置。
-
首先，"文本串"與"模式串"頭部對(duì)齊，從尾部開始比較。"S"與"E"不匹配。這時(shí)，"S"就被稱為"壞字符"（bad character），即不匹配的字符，它對(duì)應(yīng)著模式串的第6位。且"S"不包含在模式串"EXAMPLE"之中（相當(dāng)于最右出現(xiàn)位置是-1），這意味著可以把模式串后移6-(-1)=7位，從而直接移到"S"的后一位。
-
依然從尾部開始比較，發(fā)現(xiàn)"P"與"E"不匹配，所以"P"是"壞字符"。但是，"P"包含在模式串"EXAMPLE"之中。因?yàn)椤癙”這個(gè)“壞字符”對(duì)應(yīng)著模式串的第6位（從0開始編號(hào)），且在模式串中的最右出現(xiàn)位置為4，所以，將模式串后移6-4=2位，兩個(gè)"P"對(duì)齊。
-
依次比較，得到 “MPLE”匹配，稱為"好后綴"（good suffix），即所有尾部匹配的字符串。注意，"MPLE"、"PLE"、"LE"、"E"都是好后綴。
-
發(fā)現(xiàn)“I”與“A”不匹配：“I”是壞字符。如果是根據(jù)壞字符規(guī)則，此時(shí)模式串應(yīng)該后移2-(-1)=3位。問題是，有沒有更優(yōu)的移法？
-
更優(yōu)的移法是利用好后綴規(guī)則：當(dāng)字符失配時(shí)，后移位數(shù) = 好后綴在模式串中的位置 - 好后綴在模式串中上一次出現(xiàn)的位置，且如果好后綴在模式串中沒有再次出現(xiàn)，則為-1。所有的“好后綴”（MPLE、PLE、LE、E）之中，只有“E”在“EXAMPLE”的頭部出現(xiàn)，所以后移6-0=6位。可以看出，“壞字符規(guī)則”只能移3位，“好后綴規(guī)則”可以移6位。每次后移這兩個(gè)規(guī)則之中的較大值。這兩個(gè)規(guī)則的移動(dòng)位數(shù)，只與模式串有關(guān)，與原文本串無關(guān)。
-
繼續(xù)從尾部開始比較，“P”與“E”不匹配，因此“P”是“壞字符”，根據(jù)“壞字符規(guī)則”，后移 6 - 4 = 2位。因?yàn)槭亲詈笠晃痪褪?，尚未獲得好后綴。
（彩蛋）BMH算法——省去好后綴表的優(yōu)化算法
BMH它不再像BM算法一樣關(guān)注失配的字符(好后綴)，它的關(guān)注的焦點(diǎn)在于這個(gè)壞字符上，根據(jù)這個(gè)字符在模式串P中出現(xiàn)的最后的位置算出偏移長度，否則偏移模式串的長度。
研究表明，壞字符表在匹配過程中占主導(dǎo)作用的概率為94.03%（其實(shí)腦子里想想就知道了），遠(yuǎn)高于好后綴表的使用。同時(shí)相對(duì)來說好后綴表的計(jì)算過程相對(duì)復(fù)雜。BMH算法從減少比較次數(shù)來提高BM算法的性能。
- 字符X不在模板P中，則跳躍的步數(shù)為模板P的長度
-
字符X在模板P中，跳躍的步數(shù)為字符X距離離尾部最近的字符X的距離（不包括最后一個(gè)字符）
const int maxNum = 1005;
int shift[maxNum];
int BMH(const string& T, const string& P) {
int n = T.length();
int m = P.length();
// 默認(rèn)值，主串左移m位
for(int i = 0; i < maxNum; i++) {
shift[i] = m;
}
// 模式串P中每個(gè)字母出現(xiàn)的最后的下標(biāo)，最后一個(gè)字母除外
// 主串從不匹配最后一個(gè)字符，所需要左移的位數(shù)
for(int i = 0; i < m - 1; i++) {
shift[P[i]] = m - i - 1;
}
// 模式串開始位置在主串的哪里
int s = 0;
// 從后往前匹配的變量
int j;
while(s <= n - m) {
j = m - 1;
// 從模式串尾部開始匹配
while(T[s + j] == P[j]) {
j--;
// 匹配成功
if(j < 0) {
return s;
}
}
// 找到壞字符(當(dāng)前跟模式串匹配的最后一個(gè)字符)
// 在模式串中出現(xiàn)最后的位置(最后一位除外)
// 所需要從模式串末尾移動(dòng)到該位置的步數(shù)
s = s + shift[T[s + m - 1]];
}
return -1;
}
6. Sunday算法(直接復(fù)制過來的)
上文中，我們已經(jīng)介紹了KMP算法和BM算法，這兩個(gè)算法在最壞情況下均具有線性的查找時(shí)間。但實(shí)際上，KMP算法并不比最簡單的c庫函數(shù)strstr()快多少，而BM算法雖然通常比KMP算法快，但BM算法也還不是現(xiàn)有字符串查找算法中最快的算法，本文最后再介紹一種比BM算法更快的查找算法即Sunday算法。
Sunday算法由Daniel M.Sunday在1990年提出，它的思想跟BM算法很相似：
只不過Sunday算法是從前往后匹配，在匹配失敗時(shí)關(guān)注的是文本串中參加匹配的最末位字符的下一位字符。
如果該字符沒有在模式串中出現(xiàn)則直接跳過，即移動(dòng)位數(shù) = 匹配串長度 + 1；
否則，其移動(dòng)位數(shù) = 模式串中最右端的該字符到末尾的距離+1。
下面舉個(gè)例子說明下Sunday算法。假定現(xiàn)在要在文本串"substring searching algorithm"中查找模式串"search"。
- 剛開始時(shí)，把模式串與文本串左邊對(duì)齊：
s u b s t r ing searching algorithm
s e a r c h - 結(jié)果發(fā)現(xiàn)在第2個(gè)字符處發(fā)現(xiàn)不匹配，不匹配時(shí)關(guān)注文本串中參加匹配的最末位字符的下一位字符，即標(biāo)粗的字符 i，因?yàn)槟Ｊ酱畇earch中并不存在i，所以模式串直接跳過一大片，向右移動(dòng)位數(shù) = 匹配串長度 + 1 = 6 + 1 = 7，從 i 之后的那個(gè)字符（即字符n）開始下一步的匹配，如下圖：
substri n g _ s e a rching algorithm
s e a r c h
結(jié)果第一個(gè)字符就不匹配，再看文本串中參加匹配的最末位字符的下一位字符，是'r'，它出現(xiàn)在模式串中的倒數(shù)第3位，于是把模式串向右移動(dòng)3位（r 到模式串末尾的距離 + 1 = 2 + 1 =3），使兩個(gè)'r'對(duì)齊，如下：
substring s e a r c h ing algorithm
s e a r c h匹配成功。
回顧整個(gè)過程，我們只移動(dòng)了兩次模式串就找到了匹配位置，緣于Sunday算法每一步的移動(dòng)量都比較大，效率很高。完。
