寫在前面
字符串的一種基本操作是子字符串查找：給定一端長度為N的文本字符串text和一個長度為M(M<N)的模式字符串pattern扯旷，在文本字符串中查找和該模式字符串相同的子字符串。在這互聯(lián)網(wǎng)時代折晦，字符串查找的需求在很多情景都需要吕粗，如在文本編輯器或?yàn)g覽器查找某個單詞胰挑、在通信內(nèi)容中截取感興趣的模式文本等等。
子字符串查找最簡單的實(shí)現(xiàn)肯定是暴力查找：
public static int search(String text, String pattern) {
int N = text.length();
int M = pattern.length();
for (int i = 0; i < N-M; i++) {
int j;
for (j = 0; j < M; j++) {
if (text.charAt(i+j) != pattern.charAt(j))
break;
}
if (j == M) return i;
}
return -1;
}
可以看到，暴力查找的最壞時間復(fù)雜度為O(N*M)嘶炭，實(shí)際應(yīng)用中往往文本字符串很長（成萬上億個字符），而模式字符串很短逊桦，這樣暴力算法的時間復(fù)雜度是無法接受的眨猎。
為了改進(jìn)查找時間，人們發(fā)明了很多字符串查找算法卫袒，而今天的主角BM算法（Bob Boyer和J Strother Moore發(fā)明宵呛，簡稱BM算法）就是其中的一種。
正文
不同于暴力查找算法的逐個字符對比夕凝，BM算法充分使用預(yù)處理模式字符串的信息來盡可能跳過更多的字符宝穗。在暴力算法中，比較一個字符串都是從首字母開始码秉，逐個比較下去逮矛。一旦發(fā)現(xiàn)有不同的字符，就需要從頭開始進(jìn)行下一次比較转砖，就需要將字串中的所有字符一一比較须鼎。BM算法的核心思路在于，文本字符串從左到右檢索府蔗，模式字符串從右到左檢索晋控，當(dāng)模式字符串的一個字符pattern[j]和文本字符串的字符text[i+j]不匹配時，那么在模式字符串中查找字符text[i+j]是否存在索引k姓赤，使得pattern[k] == text[i+j]赡译，k若存在，k應(yīng)該為滿足條件的最右索引不铆。此時存在三種情景：
- 情景1：若pattern不存在索引k(0 <= K < M)蝌焚，使得pattern[k] == text[i+j]裹唆，那么text[i, i+j]不可能跟pattern匹配，那么i向右平移j+1只洒。如圖1所示许帐。
- 情景2：若pattern存在索引k(0 <= K < M)，使得pattern[k] == text[i+j]毕谴，此時又有兩種子情景：
- 情景2.1：k < j成畦，把text[i+j]對齊pattern[k]，也即把i向右平移j-k析珊。如圖2所示羡鸥。
- 情景2.2：k > j，顯然i不能減少忠寻，那么把i加1惧浴。如圖3所示。
通過這種字符的移動方式來代替逐個比較奕剃，正是BM算法的高效的關(guān)鍵所在衷旅！那么我們怎么知道文本字符串的字符是否存在于模式字符串中？對的纵朋，預(yù)處理柿顶。我們在查找前，先建立一張包含文本字符串的所有字符的字母表操软，這張表中記錄著字母表中的每個字符在模式字符串中出現(xiàn)的最靠右的索引嘁锯，如果在字符在模式字符串中不存在，那么值為-1聂薪。
有了這張表家乘，我們在查找時就可以高效的移動i。構(gòu)建這張表很簡單：
// 構(gòu)建right數(shù)組
int R = 256; // 字母表大小藏澳，這里用ASCII字母表舉例
int[] right = new int[R]; // 記錄字母表中的每個字符在模式字符串中出現(xiàn)的最右的索引
for (int i = 0; i < R; i++)
right[i] = -1;
for (int j = 0; j < M; j++)
right[pattern.charAt(j)] = j;
構(gòu)建好表仁锯，我們只需要按上面分析的情景，出現(xiàn)字符不匹配時翔悠，通過表业崖，把i向右平移到具體位置即可。BM完整算法實(shí)現(xiàn)如下：
public static int search(String text, String pattern) {
int N = text.length();
int M = pattern.length();
// 構(gòu)建right數(shù)組
int R = 256; // 字母表大小
int[] right = new int[R]; // 記錄字母表中的每個字符在模式字符串中出現(xiàn)的最右的索引
for (int i = 0; i < R; i++)
right[i] = -1;
for (int j = 0; j < M; j++)
right[pattern.charAt(j)] = j;
int skip;
for (int i = 0; i <= N-M; i+=skip) {
skip = 0;
for (int j = M-1; j >= 0; j--) {
if (pattern.charAt(j) != text.charAt(i+j)) { // 不匹配的情況
skip = j - right[text.charAt(i + j)]; // 這里包括情景1和情景2.1蓄愁，如果情景1双炕，right[text.charAt(i + j)]為-1
if (skip < 1) skip = 1; // 情景2.2
break;
}
}
if (skip == 0) return i; // 匹配成功
}
return -1; // 未找到匹配
}
由于不匹配的情況屬于大多數(shù)，所以一般情況下撮抓，BM算法的時間復(fù)雜度為O(N/M)妇斤，是線性級別的！可以說是非常高效了。但它需要額外的空間字母表大小R趟济，所以BM算法是以空間換時間的。
至此咽笼，BM字符串查找算法已經(jīng)分析完了顷编，其實(shí)算是一種比較簡單的算法，學(xué)習(xí)起來很快就能搞懂～
寫在最后
參考
- 《算法：第四版》
