共計 3349 個字符，預計需要花費 9 分鐘才能閱讀完成。
Boyer Moore 算法怎么用，相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。
簡介
對于字符串的搜索算法，我曾經討論過 KMP 算法的思路和實現。KMP 算法的實現思路是基于模式串里面的的前綴和后綴匹配，這種算法的效率已經足夠快了。沒想到的是，這里我們要討論的 Boyer Moore 算法效率更加驚人。
思路分析
在之前的算法里，我們是通過從模式串的開頭到結尾這么一個個的去和目標串比較，這種方式在碰到匹配的元素時則繼續比較下一個，在沒有匹配的時候，則通過查找模式表構建的匹配表來選擇模式串里后面的第幾個元素來繼續進行比較。這樣目標串里的索引就不用往回挪。但是，這里比較的順序恰好相反。假設目標串長度為 n, 模式串長度為 m。那么，首先我們就從兩個串的 m – 1 索引位置開始比較，如果相同，則一直向前，如果不同，則需要根據這個不同的字符的情況來判斷。
根據比較字符的不同，我們可能有兩種情況，一種是這個不同的字符不在模式串里。那么很顯然，模式串里任何一個字符都不可能和它匹配的，我們只需要跳到這個字符的后面那個位置開始繼續比較就可以了。還有一種情況就是這個字符是在模式串里的，那么，我們就需要找到和這個字符匹配的最后一個出現在模式串里的字符。這樣，我們可以在模式串中從最后匹配的位置開始繼續往后比較。
前面的這部分描述顯得比較抽象，我們可以結合一個具體的示例來討論。假設我們有字符串 s 和 p，s 的值為：FINDINAHAYSTACKNEEDLEINA, p 的值為: NEEDLE。我們分別用 i, j 來表示 s, p 當前的位置。那么，他們比較的過程如下圖：
結合上圖來說，他們最開始比較的位置是從索引 5 開始。這個時候 s 在這個位置的元素是 N，而 p 在這個位置的字符是 E。那么他們并不匹配。我們就需要跳到后面進行比較。而這個字符 N 在 p 里面是存在的，對應 p 里最后出現 N 的位置就是索引 0。所以我們就從 N 的這個位置開始到 p 最末尾的位置作為比較的點，又從 p 的末尾和對應的 s 的位置進行比較。這個時候 i 的索引位置為 10 的時候它和 p 最末尾的字符 E 并不匹配，而且這個字符是 S，在 p 串里也找不到對應的字符。那么這時候，我們就需要從 S 后面的元素開始和 p 的第一個元素對齊，然后我們再從 p 的最后一個元素以及 s 串的索引 i + j 進行比較。這時候一直比較到開頭，發現有匹配的串。于是返回 i = 15。
概括
經過上述的討論，我們發現，要實現這個算法需要考慮的就是怎么用一種比較簡單的方法將字符串的匹配和不匹配場景給統一起來。這樣在每次比較到匹配或者不匹配的時候能夠對應的調整。對于前面的場景我們來仔細看一下。
當比較的字符和當前 p 模式串里的字符不匹配時，如果這個不匹配的字符也不在模式串里，那么這種情形的調整如下圖：
因為這種情況下，無論取模式串里的那個元素都不可能和這個元素匹配的，所以相當于要將整個模式串挪到這個元素的后面的那個位置對齊再來比較。這個時候，相當于將 j 重置到 m – 1 的值，而這個時候 i 的值也調整到 i + j + 1。
還有一種情況就是這個當前不匹配的字符在模式串里，如下圖：
在這個示例里，因為不匹配的字符是 N，但是 N 存在于模式串中。所以我們需要將 i 所在的位置移動到這個不匹配元素的位置。而這個時候模式串里的位置是 j，如果我們可以找到 N 所在的索引位置，就可以通過 j – right[N] 來實現了。
所以總的來說，我們在比較的時候對于目標串的索引 i 和模式串的索引 j 來說，它們比較和調整順序正好相反。i 是逐步遞增的調整，而 j 是遞減的進行比較。當 s.charAt(i + j) == p.charAt(j) 的時候，表示它們匹配。所以這時候繼續進行個 j – 這個操作進行下一步比較就可以。而 s.charAt(i + j) != p.charAt(j) 的時候，就要調整了。根據前面的討論，如果 s.charAt(i + j) 不存在于 p 中間，這個時候，我們需要將 i 往右移動 j + 1 個位置。按照前面討論的，也就是 j – right[s.charAt(i + j)]。這也說明了 right[s.charAt(i + j)] 為 -1。
而如果 s.charAt(i + j) 存在于模式串中，那么我們需要找到這個字符在模式串中間的位置，我們需要移動的距離就是從 j 到這個字符的距離。如果用 j – right[s.charAt(i + j)]，那么這里 right[s.charAt(i + j)] 記錄的應該就是字符 s.charAt(i + j) 在模式串中的位置。
這樣，我們將 right[] 數組記錄的值統一起來了。問題的核心就歸結為怎么計算 right 數組。
計算 right
計算 right 數組的過程比較簡單，因為只要記錄每個字符在模式串里最后出現的位置就可以了。對于不在模式串里的元素呢，只要設置為 - 1 就可以了。所以我們可以用如下一段代碼實現：
right = new int[r];
for(int c = 0; c r; c++)
right[c] = -1;
for(int j = 0; j m; j++)
right[pat.charAt(j)] = j;
最終實現
剩下的就是將整個實現給連貫起來。建立好 right 數組之后，剩下的就是從目標串 i 開始，每次比較 s[i + j] 和 p[j] 的位置。如果相等，就繼續比較，直到 j == 0。如果不等，則計算 i 后面要移動的距離 skip，其中 skip = j – right[s[i + j]]。這樣，詳細的實現如下：
public class BoyerMoore {
private int[] right;
private String pat;
public BoyerMoore(String pat) {
this.pat = pat;
int m = pat.length();
int r = 256;
right = new int[r];
for(int c = 0; c r; c++)
right[c] = -1;
for(int j = 0; j m; j++)
right[pat.charAt(j)] = j;
}
public int search(String txt) {
int n = txt.length();
int m = pat.length();
int skip;
for(int i = 0; i = n – m; i+= skip) {
skip = 0;
for(int j = m – 1; j = 0; j–) {
if(pat.charAt(j) != txt.charAt(i + j)) {
skip = j – right[txt.charAt(i + j)];
if(skip 1) skip = 1;
break;
}
}
if(skip == 0) return i;
}
return -1;
}
}
在上述的代碼實現里，還有一個值得注意的小細節，就是計算出 skip 之后，要判斷 skip 是否小于 1。因為有可能碰到的當前不匹配字符是存在于模式串里，但是它最后出現的位置要大于當前的值 j 了。這時候，我們要保證 i 最少要移動一位。所以這里要設置為 1。
還有一個需要注意的地方就是，因為要考慮到為每個字符建立它的映射關系，所以我們需要建立一個有字符集長度那么長的 right 數組。在字符集太大的情況下，它占用的空間會比較多。這里只是針對理想的 256 個字符的情況建立的 right 表。
從該算法的性能來說，它在理想的情況下的時間復雜度為 O(M/N) 其中 M 是目標串的長度，而 N 是模式串的長度。
Boyer Moore 算法是一個在實際中應用比較廣泛的算法，它的速度更加快。和其他的字符串匹配方法比起來，它采用從后面往前的比較方式。同時通過建立一個字符映射表來保存字符在當前模式串里的位置，以方便每次比較的時候源串的位置調整。它最大的特點就是不再是一個個字符的移動，而是根據計算一次跳過若干個字符。這樣總體的性能比較理想。
看完上述內容，你們掌握 Boyer Moore 算法怎么用的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注丸趣 TV 行業資訊頻道，感謝各位的閱讀！
