一陨界、BM算法定義
BM（Boyer-Moore）算法栏赴，它和KMP算法一樣都是從主串的最左端開始盈咳，然后不斷右移的耿眉。
與KMP算法的不同之處在于：BM算法從右向左掃描模式字符串，并將它和文本字符串比較鱼响。
BM算法的效率比KMP算法高很多鸣剪，常用于文本編輯器中的搜索匹配功能。
二丈积、基本思想
2.1 壞字符與好后綴
BM算法中存在兩個概念：壞字符與好后綴
壞字符（Bad Character）
所謂壞字符筐骇，就是模式串與文本串在從右往左的匹配過程中，出現(xiàn)的第1個不匹配的文本字符桶癣。（如圖2-1中的b）
那么拥褂，當匹配過程中出現(xiàn)“壞字符”如何處理？
應(yīng)當將模式字符串右移牙寞，直至遇到一個與壞字符相同的模式字符或最終移動到壞字符+1位置（即沒有遇到與壞字符匹配的模式字符）,如下圖：
好后綴（Good Suffix）
所謂好后綴饺鹃，就是模式串與文本串在從右往左的匹配過程中莫秆，出現(xiàn)的部分匹配的文本字符串后綴（如圖2-1中的a、ba悔详、aba）
那么镊屎，當匹配過程中出現(xiàn)“好后綴”如何處理？
應(yīng)當將模式字符串右移茄螃，直至模式字符串與好后綴完全匹配或部分匹配或不匹配缝驳，如下圖：
綜上所述，在匹配過程中归苍，如果當前字符匹配失敗用狱，則：
模式字符串右移位數(shù) = Max { shift(壞字符) , shift(好后綴) }
2.2 算法示例
以字符串"HERE IS A SIMPLE EXAMPLE"，模式字符串"EXAMPLE"為例拼弃。
- 首先夏伊，文本與模式串頭部對齊，從尾部開始比較吻氧，發(fā)現(xiàn)"S"與"E"不匹配溺忧，所以"S"是"壞字符"，且不存在好后綴盯孙。
由于模式串左側(cè)中不存在與壞字符“S”相同的字符鲁森，故模式字符串右移至"S"位置+1，shift('S')=7振惰，即模式字符串右移位數(shù) = Max { 7, 0}=7
- 再次從尾部開始比較歌溉，發(fā)現(xiàn)"P"與"E"不匹配，所以"P"是"壞字符"骑晶，且不存在好后綴研底。
但是，模式串左側(cè)“EXAMPL”中存在相同的字符"P"透罢，故shift('P')=2，即模式字符串右移位數(shù) = Max { 2, 0}=2
- 依然從尾部開始比較冠蒋，"MPLE"與"MPLE"匹配羽圃，直到"I"和"A"不匹配，所以"I"是"壞字符"抖剿，且存在好后綴"MPLE"朽寞。
- 此時"I"和"A"不匹配，模式串左側(cè)“EX”中不存在與壞字符"I"相同的字符斩郎，故
shift('I')=3脑融；
模式字符串中存在與好后綴“MPLE”部分匹配的"E"，故shift('E')=6缩宜，模式字符串右移位數(shù) = Max { 6, 3}=6
- 依然從尾部開始比較肘迎，"P"和"E"不匹配甥温，所以"P"是"壞字符"，且不存在好后綴妓布。
但是姻蚓，模式串左側(cè)“EXAMPL”中存在相同的字符"P"，故shift('P')=2匣沼，即模式字符串右移位數(shù) = Max { 2, 0}=2
- 然后再次從尾部開始逐位比較狰挡，發(fā)現(xiàn)全部匹配，于是搜索結(jié)束释涛。
三加叁、算法實現(xiàn)
BM算法在從右向左的比較過程中，當某個字符失配時唇撬，需要分別按壞字符算法 和好后綴算法 計算模式串需要右移的距離它匕，然后取最大值，進行右移局荚。
3.1 壞字符算法
/**
* 構(gòu)造壞字符數(shù)組
* bmBC['k']表示壞字符'k'在模式串中的最右位置超凳，如不存在則為-1
*/
public int[] getBmBc(String ptn) {
int[] bmBc = new int[R]; // R為字母表大小
for (int c = 0; c < R; c++) {
bmBc[c] = -1;
}
for (int i = 0; i < ptn.length(); i++) {
bmBc[ptn.charAt(i)] = i;
}
return bmBc;
}
位移數(shù)(Shift) = 壞字符在當前模式串中的索引 - bmBC[壞字符];
(如果結(jié)果小于0，則置為1耀态，因為模式串不能左移)
3.2 好后綴算法
1轮傍、構(gòu)建輔助數(shù)組suffix[]：
suffix[i] = s 表示字符P[i]之前的子串，與模式串后綴匹配的最大長度首装，如下圖所示创夜，用公式可以描述：滿足P[i-s, i] == P[m-s, m]的最大長度s。
* 構(gòu)建輔助后綴數(shù)組
* suffix[i] = n 表示模式字符P[i]之前的子串仙逻，與模式串后綴匹配的最大長度為n
*/
private int[] getSuffix(String ptn) {
int m = ptn.length();
int[] suffix = new int[m];
suffix[m - 1] = m;
for (int i = m - 2; i >= 0; i--) { // i指向當前求解的字符
int n = 0; // 記錄相同后綴數(shù)量
int k1 = i, k2 = m - 1;
while (k1 >= 0 && k2 >= 0 && ptn.charAt(k1) == ptn.charAt(k2))
n++;
suffix[i] = n;
}
return suffix;
}
2驰吓、構(gòu)建好后綴數(shù)組bmGs[]：
bmGs[i]表示遇到好后綴時，模式串應(yīng)該右移的距離系奉，其中i表示當前匹配失效的字符位置（也就是當前壞字符的位置）檬贰。
分為三種情況：
- 模式串中無任何字符與好后綴匹配（這種情況右移距離最長）
- 模式串中有前綴與好后綴部分匹配（這種情況右移距離次長）
- 模式串中有子串與好后綴完全匹配（這種情況右移距離最短）
綜上，我們應(yīng)該盡量讓一次移動的距離少一點缺亮，以免回退翁涤。
/**
* 求解bmGs數(shù)組
* bmGs[i]表示遇到好后綴時，模式串應(yīng)該右移的距離萌踱，其中i表示好后綴前面一個字符的位置（也就是當前壞字符的位置）
*/
private int[] getBmGs(String ptn) {
int m = ptn.length();
int[] bmGs = new int[m];
int[] suffix = getSuffix(ptn);
// 1.模式串中無任何字符與好后綴匹配（這種情況右移距離最長）
for (int i = 0; i < m; i++) {
bmGs[i] = m;
}
// 2.模式串中有前綴與好后綴部分匹配（這種情況右移距離次長）
for (int i = m - 1; i >= 0; i--) {
if (suffix[i] == i + 1) {
for (int j = 0; j < m - 1 - i; j++) {
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
}
}
}
// 3.模式串中有子串與好后綴完全匹配（這種情況右移距離最短）
for (int i = 0; i < m - 1; i++) {
bmGs[m - 1 - suffix[i]] = m - 1 - i;
}
return bmGs;
}
3.3 BM算法完整實現(xiàn)
public int search(String txt, String ptn) {
int n = txt.length();
int m = ptn.length();
int[] bmBc = getBmBc(ptn); // 壞字符算法
int[] bmGs = getBmGs(ptn); // 好后綴算法
int i = 0, j = m - 1; // 指針i追蹤文本葵礼，指針j追蹤模式字符串
while (i <= n - m) {
j = m - 1; // 每次失配后，j重置為起始位置
while (j >= 0 && ptn.charAt(j) == txt.charAt(i + j))
j--;
if (j < 0) // 完全匹配成功
return i;
else {
char badChar = txt.charAt(i + j); // i+j指向了當前正在比較的文本字符（壞字符）
// 壞字符算法
int len1 = j - bmBc[badChar] < 0 ? 1 : j - bmBc[badChar];
// 好后綴算法
int len2 = bmGs[badChar];
// 取最大位移
i += max(len1, len2); // 匹配失敗
}
}
return -1;
}
四并鸵、性能分析
預(yù)處理階段
時間復(fù)雜度和空間復(fù)雜度都是O(M)搜索階段
時間復(fù)雜度：O(MN)
最好情況下：O(N/M)
注：N為文本串長度鸳粉，M為模式串長度
