BF,BM,KMP，就這？
為保證代碼嚴謹性，文中所有代碼均在 leetcode 刷題網站 AC ，大家可以放心食用。
皇上生辰之際，舉國同慶，袁記菜館作為天下第一飯店，所以被選為這次慶典的菜品供應方，這次慶典對於袁記菜館是一項前所未有的挑戰，畢竟是第一次給皇上慶祝生辰，稍有不慎就是掉腦袋的大罪，整個袁記菜館內都在緊張的布置着。此時突然有一個店小二慌慌張張跑到袁廚面前彙報，到底發生了什麼事，讓店小二如此慌張呢？
袁記菜館內
店小二：不好了不好了，掌柜的，出大事了。
袁廚：發生什麼事了，慢慢說，如此慌張，成何體統。（開店開久了，架子出來了哈）
店小二：皇上按照咱們菜單點了 666 道菜，但是咱們做西湖醋魚的師傅請假回家結婚了，不知道皇上有沒有點這道菜，如果點了這道菜，咱們做不出來，那咱們店可就完了啊。
（袁廚聽了之後，嚇得一屁股坐地上了，緩了半天說道）
袁廚：別說那麼多了，快給我找找皇上點的菜裏面，有沒有這道菜！
找了很久，並且核對了很多遍，最後確認皇上沒有點這道菜。菜館內的人都鬆了一口氣
通過上面的一個例子，讓我們簡單了解了字符串匹配。
字符串匹配：設 S 和 T 是給定的兩個串，在主串 S 中找到模式串 T 的過程稱為字符串匹配，如果在主串 S 中找到 模式串 T ，則稱匹配成功，函數返回 T 在 S 中首次出現的位置，否則匹配不成功，返回 -1。
例：
在上圖中，我們試圖找到模式 T = baab,在主串 S = abcabaabcabac 中第一次出現的位置，即為紅色陰影部分， T 第一次在 S 中出現的位置下標為 4 （ 字符串的首位下標是 0 ），所以返回 4。如果模式串 T 沒有在主串 S 中出現，則返回 -1。
解決上面問題的算法我們稱之為字符串匹配算法，今天我們來介紹三種字符串匹配算法，大家記得打卡呀，說不準面試的時候就問到啦。
BF算法（Brute Force）
這個算法很容易理解，就是我們將模式串和主串進行比較，一致時則繼續比較下一字符，直到比較完整個模式串。不一致時則將模式串後移一位，重新從模式串的首位開始對比，重複剛才的步驟下面我們看下這個方法的動圖解析，看完肯定一下就能搞懂啦。
因為不
通過上面的代碼是不是一下就將這個算法搞懂啦，下面我們用這個算法來解決下面這個經典題目吧。
leetcdoe 28. 實現 strStr()
題目描述
給定一個 haystack 字符串和一個 needle 字符串，在 haystack 字符串中找出 needle 字符串出現的第一個位置 (從0開始)。如果不存在，則返回 -1。
示例 1:
輸入: haystack = “hello”, needle = “ll”
輸出: 2
示例 2:
輸入: haystack = “aaaaa”, needle = “bba”
輸出: -1
題目解析
其實這個題目很容易理解，但是我們需要注意的是一下幾點，比如我們的模式串為 0 時，應該返回什麼，我們的模式串長度大於主串長度時，應該返回什麼，也是我們需要注意的地方。下面我們來看一下題目代碼吧。
題目代碼
class Solution {
public int strStr(String haystack, String needle) {
int haylen = haystack.length();
int needlen = needle.length();
//特殊情況
if (haylen < needlen) {
return -1;
}
if (needlen == 0) {
return 0;
}
//主串
for (int i = 0; i < haylen - needlen + 1; ++i) {
int j;
//模式串
for (j = 0; j < needlen; j++) {
//不符合的情況，直接跳出，主串指針後移一位
if (haystack.charAt(i+j) != needle.charAt(j)) {
break;
}
}
//匹配成功
if (j == needlen) {
return i;
}
}
return -1;
}
}
我們看一下BF算法的另一種算法（顯示回退），其實原理一樣，就是對代碼進行了一下修改，只要是看完咱們的動圖，這個也能夠一下就能看懂，大家可以結合下面代碼中的注釋和動圖進行理解。
class Solution {
public int strStr(String haystack, String needle) {
//i代表主串指針，j模式串
int i,j;
//主串長度和模式串長度
int halen = haystack.length();
int nelen = needle.length();
//循環條件，這裡只有 i 增長
for (i = 0 , j = 0; i < halen && j < nelen; ++i) {
//相同時，則移動 j 指針
if (haystack.charAt(i) == needle.charAt(j)) {
++j;
} else {
//不匹配時，將 j 重新指向模式串的頭部，將 i 本次匹配的開始位置的下一字符
i -= j;
j = 0;
}
}
//查詢成功時返回索引，查詢失敗時返回 -1；
int renum = j == nelen ? i - nelen : -1;
return renum;
}
}
BM算法(Boyer-Moore)
我們剛才說過了 BF 算法，但是 BF 算法是有缺陷的，比如我們下面這種情況
如上圖所示，如果我們利用 BF 算法，遇到不匹配字符時，每次右移一位模式串，再重新從頭進行匹配，我們觀察一下，我們的模式串 abcdex 中每個字符都不一樣，但是我們第一次進行字符串匹配時，abcde 都匹配成功，到 x 時失敗，又因為模式串每位都不相同，所以我們不需要再每次右移一位，再重新比較，我們可以直接跳過某些步驟。如下圖
我們可以跳過其中某些步驟，直接到下面這個步驟。那我們是依據什麼原則呢？
壞字符規則
我們之前的 BF 算法是從前往後進行比較 ，BM 算法是從後往前進行比較，我們來看一下具體過程，我們還是利用上面的例子。
BM 算法是從後往前進行比較，此時我們發現比較的第一個字符就不匹配，我們將主串這個字符稱之為壞字符，也就是 f ,我們發現壞字符之後，模式串 T 中查找是否含有該字符（f），我們發現並不存在 f，此時我們只需將模式串右移到壞字符的後面一位即可。如下圖
那我們在模式串中找到壞字符該怎麼辦呢？
此時我們的壞字符為 f ,我們在模式串中，查找發現含有壞字符 f,我們則需要移動模式串 T ,將模式串中的 f 和壞字符對齊。見下圖。
然後我們繼續從右往左進行比較，發現 d 為壞字符，則需要將模式串中的 d 和壞字符對齊。
那麼我們在來思考一下這種情況，那就是模式串中含有多個壞字符怎麼辦呢？
那麼我們為什麼要讓最靠右的對應元素與壞字符匹配呢？如果上面的例子我們沒有按照這條規則看下會產生什麼問題。
如果沒有按照我們上述規則，則會漏掉我們的真正匹配。我們的主串中是含有 babac 的，但是卻沒有匹配成功，所以應該遵守最靠右的對應字符與壞字符相對的規則。
我們上面一共介紹了三種移動情況，分別是下方的模式串中沒有發現與壞字符對應的字符，發現一個對應字符，發現兩個。這三種情況我們分別移動不同的位數，那我們是根據依據什麼來決定移動位數的呢？下面我們給圖中的字符加上下標。見下圖
下面我們來考慮一下這種情況。
此時這種情況肯定是不行的，不往右移動，甚至還有可能左移，那麼我們有沒有什麼辦法解決這個問題呢？繼續往下看吧。
好後綴規則
好後綴其實也很容易理解，我們之前說過 BM 算法是從右往左進行比較，下面我們來看下面這個例子。
這裡如果我們按照壞字符進行移動是不合理的，這時我們可以使用好後綴規則，那麼什麼是好後綴呢？
BM 算法是從右往左進行比較，發現壞字符的時候此時 cac 已經匹配成功，在紅色陰影處發現壞字符。此時已經匹配成功的 cac 則為我們的好後綴，此時我們拿它在模式串中查找，如果找到了另一個和好後綴相匹配的串，那我們就將另一個和好後綴相匹配的串 ，滑到和好後綴對齊的位置。
是不是感覺有點拗口，沒關係，我們看下圖，紅色代表壞字符，綠色代表好後綴
上面那種情況搞懂了，但是我們思考一下下面這種情況
上面我們說到了，如果在模式串的頭部沒有發現好後綴，發現好後綴的子串也可以。但是為什麼要強調這個頭部呢？
我們下面來看一下這種情況
但是當我們在頭部發現好後綴的子串時，是什麼情況呢？
下面我們通過動圖來看一下某一例子的具體的執行過程
視頻
說到這裡，壞字符和好後綴規則就算說完了，壞字符很容易理解，我們對好後綴總結一下
1.如果模式串含有好後綴，無論是中間還是頭部可以按照規則進行移動。如果好後綴在模式串中出現多次，則以最右側的好後綴為基準。
2.如果模式串頭部含有好後綴子串則可以按照規則進行移動，中間部分含有好後綴子串則不可以。
3.如果在模式串尾部就出現不匹配的情況，即不存在好後綴時，則根據壞字符進行移動，這裡有的文章沒有提到，是個需要特別注意的地方，我是在這個論文里找到答案的，感興趣的同學可以看下。
Boyer R S，Moore J S. A fast string searching algorithm［J］. Communications of the ACM，1977，10： 762-772.
之前我們剛開始說壞字符的時候，是不是有可能會出現負值的情況，即往左移動的情況，所以我們為了解決這個問題，我們可以分別計算好後綴和壞字符往後滑動的位數（好後綴不為 0 的情況），然後取兩個數中最大的，作為模式串往後滑動的位數。
這破圖畫起來是真費勁啊。下面我們來看一下算法代碼，代碼有點長，我都標上了注釋也在網站上 AC 了，如果各位感興趣可以看一下，不感興趣理解壞字符和好後綴規則即可。可以直接跳到 KMP 部分
class Solution {
public int strStr(String haystack, String needle) {
char[] hay = haystack.toCharArray();
char[] need = needle.toCharArray();
int haylen = haystack.length();
int needlen = need.length;
return bm(hay,haylen,need,needlen);
}
//用來求壞字符情況下移動位數
private static void badChar(char[] b, int m, int[] bc) {
//初始化
for (int i = 0; i < 256; ++i) {
bc[i] = -1;
}
//m 代表模式串的長度，如果有兩個 a,則後面那個會覆蓋前面那個
for (int i = 0; i < m; ++i) {
int ascii = (int)b[i];
bc[ascii] = i;//下標
}
}
//用來求好後綴條件下的移動位數
private static void goodSuffix (char[] b, int m, int[] suffix,boolean[] prefix) {
//初始化
for (int i = 0; i < m; ++i) {
suffix[i] = -1;
prefix[i] = false;
}
for (int i = 0; i < m - 1; ++i) {
int j = i;
int k = 0;
while (j >= 0 && b[j] == b[m-1-k]) {
--j;
++k;
suffix[k] = j + 1;
}
if (j == -1) prefix[k] = true;
}
}
public static int bm (char[] a, int n, char[] b, int m) {
int[] bc = new int[256];//創建一個數組用來保存最右邊字符的下標
badChar(b,m,bc);
//用來保存各種長度好後綴的最右位置的數組
int[] suffix_index = new int[m];
//判斷是否是頭部，如果是頭部則true
boolean[] ispre = new boolean[m];
goodSuffix(b,m,suffix_index,ispre);
int i = 0;//第一個匹配字符
//注意結束條件
while (i <= n-m) {
int j;
//從後往前匹配，匹配失敗，找到壞字符
for (j = m - 1; j >= 0; --j) {
if (a[i+j] != b[j]) break;
}
//模式串遍歷完畢，匹配成功
if (j < 0) {
return i;
}
//下面為匹配失敗時，如何處理
//求出壞字符規則下移動的位數，就是我們壞字符下標減最右邊的下標
int x = j - bc[(int)a[i+j]];
int y = 0;
//好後綴情況，求出好後綴情況下的移動位數,如果不含有好後綴的話，則按照壞字符來
if (y < m-1 && m - 1 - j > 0) {
y = move(j, m, suffix_index,ispre);
}
//移動
i = i + Math.max(x,y);
}
return -1;
}
// j代表壞字符的下標
private static int move (int j, int m, int[] suffix_index, boolean[] ispre) {
//好後綴長度
int k = m - 1 - j;
//如果含有長度為 k 的好後綴，返回移動位數，
if (suffix_index[k] != -1) return j - suffix_index[k] + 1;
//找頭部為好後綴子串的最大長度，從長度最大的子串開始
for (int r = j + 2; r <= m-1; ++r) {
//如果是頭部
if (ispre[m-r] == true) {
return r;
}
}
//如果沒有發現好後綴匹配的串，或者頭部為好後綴子串，則移動到 m 位，也就是匹配串的長度
return m;
}
}
我們來理解一下我們代碼中用到的兩個數組，因為兩個規則的移動位數，只與模式串有關，與主串無關，所以我們可以提前求出每種情況的移動情況，保存到數組中。
KMP算法（Knuth-Morris-Pratt）
我們剛才講了 BM 算法，雖然不是特別容易理解，但是如果你用心看的話肯定可以看懂的，我們再來看一個新的算法，這個算法是考研時必考的算法。實際上 BM 和 KMP 算法的本質是一樣的，你理解了 BM 再來理解 KMP 那就是分分鐘的事啦。
我們先來看一個實例
視頻
為了讓讀者更容易理解，我們將指針移動改成了模式串移動，兩者相對與主串的移動是一致的，重新比較時都是從指針位置繼續比較。
通過上面的實例是不是很快就能理解 KMP 算法的思想了，但是 KMP 的難點不是在這裡，不過多思考，認真看理解起來也是很輕鬆的。
在上面的例子中我們提到了一個名詞，最長公共前後綴，這個是什麼意思呢？下面我們通過一個較簡單的例子進行描述。
此時我們在紅色陰影處匹配失敗，綠色為匹配成功部分，則我們觀察匹配成功的部分。
我們來看一下匹配成功部分的所有前綴
我們的最長公共前後綴如下圖，則我們需要這樣移動
好啦，看完上面的圖，KMP的核心原理已經基本搞定了，但是我們現在的問題是，我們應該怎麼才能知道他的最長公共前後綴的長度是多少呢？怎麼知道移動多少位呢？
剛才我們在 BM 中說到，我們移動位數跟主串無關，只跟模式串有關，跟我們的 bc,suffix,prefix 數組的值有關，我們通過這些數組就可以知道我們每次移動多少位啦，其實 KMP 也有一個數組，這個數組叫做 next 數組，那麼這個 next 數組存的是什麼呢？
next 數組存的咱們最長公共前後綴中，前綴的結尾字符下標。是不是感覺有點彆扭，我們通過一個例子進行說明。
我們知道 next 數組之後，我們的 KMP 算法實現起來就很容易啦，另外我們看一下 next 數組到底是幹什麼用的。
剩下的就不用說啦，完全一致啦，咱們將上面這個例子，翻譯成和咱們開頭對應的動畫大家看一下。
動畫必上岸
下面我們看一下代碼，標有詳細注釋，大家認真看呀。
註：很多教科書的 next 數組表示方式不一致，理解即可
class Solution {
public int strStr(String haystack, String needle) {
//兩種特殊情況
if (needle.length() == 0) {
return 0;
}
if (haystack.length() == 0) {
return -1;
}
// char 數組
char[] hasyarr = haystack.toCharArray();
char[] nearr = needle.toCharArray();
//長度
int halen = hasyarr.length;
int nelen = nearr.length;
//返回下標
return kmp(hasyarr,halen,nearr,nelen);
}
public int kmp (char[] hasyarr, int halen, char[] nearr, int nelen) {
//獲取next 數組
int[] next = next(nearr,nelen);
int j = 0;
for (int i = 0; i < halen; ++i) {
//發現不匹配的字符，然後根據 next 數組移動指針，移動到最大公共前後綴的，
//前綴的後一位,和咱們移動模式串的含義相同
while (j > 0 && hasyarr[i] != nearr[j]) {
j = next[j - 1] + 1;
//超出長度時，可以直接返回不存在
if (nelen - j + i > halen) {
return -1;
}
}
//如果相同就將指針同時後移一下，比較下個字符
if (hasyarr[i] == nearr[j]) {
++j;
}
//遍歷完整個模式串，返回模式串的起點下標
if (j == nelen) {
return i - nelen + 1;
}
}
return -1;
}
//這一塊比較難懂，不想看的同學可以忽略，了解大致含義即可，或者自己調試一下，看看運行情況
//我會每一步都寫上注釋
public int[] next (char[] needle,int len) {
//定義 next 數組
int[] next = new int[len];
// 初始化
next[0] = -1;
int k = -1;
for (int i = 1; i < len; ++i) {
//我們此時知道了 [0,i-1]的最長前後綴，但是k+1的指向的值和i不相同時，我們則需要回溯
//因為 next[k]就時用來記錄子串的最長公共前後綴的尾坐標（即長度）
//就要找 k+1前一個元素在next數組裡的值,即next[k+1]
while (k != -1 && needle[k + 1] != needle[i]) {
k = next[k];
}
// 相同情況，就是 k的下一位，和 i 相同時，此時我們已經知道 [0,i-1]的最長前後綴
//然後 k - 1 又和 i 相同，最長前後綴加1，即可
if (needle[k+1] == needle[i]) {
++k;
}
next[i] = k;
}
return next;
}
}
這篇文章真的寫了很久很久，覺得還不錯的話，就麻煩您點個贊吧，大家也可以去我的公眾號看我的所有文章，每個都有動圖解析，公眾號：袁廚的算法小屋
