一、简介
上文中我们介绍了一款字符串匹配的算法，此文会介绍另一款更高效的算法，据称会教KMP算法而言，效率提高了3~5倍。
该算法由 Bob Boyer 和J Strother Moore 共同创建，故称为 Boyer-Moore 字符串搜索算法，简称 BM 算法。
我们在文本文档编辑的时候，常用的搜索功能（Ctrl + F），底层算法其实就是该 BM 算法。
二、名词定义
以下摘自 wikipedia
- 被检索的字符，也就是原文，称为 text，用符号 T 表示
检索的字符串，也就是你需要搜索的字符串，称为模式串，也称为 pattern，用符号 P 表示
P 的长度记为 n
T 的长度记为 m
S[i] 为字符串 S 从1开始计数的第 i 个字符
S[i..j] 为字符串 S 的一个子串，始于i，终于j
S 的前缀定义为 S[1..i]，其中 i 小于S 的长度
S 的后缀定义为 S[i..n]，其中n 为 S 的长度
k 表示 字符串P 的最后一位在 T 中的位置
当发生匹配时，P 在 T 中的位置记为 T[(k-n+1)..k]
坏字符：T 和 P 中不匹配的字符（下文的案例中会详细介绍）
好后缀：T 和 P 中相匹配的后缀（下文的案例中会详细介绍）
三、原理简析
下面以图示的方式，来简单阐述 BM 算法的匹配步骤。
首先，相较于朴素的算法，朴素算法是从 P 的首字符开始匹配，直至出现不一致，然后再将 P 后移一定的位数。而 BM 算法的变通之处主要出现在两点上：
①BM 算法从 P 的末字符开始，依次往前进行匹配，直至出现不一致；
②此时 P 需要右移，那么右移多少位呢？该位数由两个子算法共同构成，即坏字符算法和好后缀算法，两者分别进行计算右移的位数，谁算得的右移位数多，最终 P 右移的位数便会采用。
其实，坏字符和好后缀计算的右移位数的计算，都是查询相应的表而得到的，而这两张表，就是 BM 的核心，即，该算法需要对 P 进行预处理，从而得出这两张表。
四、简明图示案例
BM 算法核心：找到一个后缀，让已匹配过的后缀与P中从后往前最近的一个相同的子串对齐。
案例一：T 为 0123456789 ， P为 MOORE
常规的匹配是先将0和M开始匹配，不一样，然后后移一位，再将1和M进行匹配，依次类推，总共需要匹配10次，或者先进一点，需要匹配6次，
而我们的 BM 算法，如果利用坏字符规则，则只需要匹配两次：
第一次直接将4和E进行匹配，出现不一致，此时我们需要将P后移，此时的4即为坏字符，那么后移多少位呢？此处根据核心：找到一个后缀，让已匹配过的后缀与P中从后往前最近的一个相同的子串对齐，而此处，由于已匹配过的后缀是4，但是这个4并没有出现在P中，所以将整个P往后移，直至P的首字符M位于4的后面，即将P往后移动5个字符，也就是往后移P的长度个字符。
另外，坏字符移动规则公式为：后移位数 = 坏字符位数 - 坏字符在P中上次出现的位置
而此处：后移位数 = 5 - 0 = 5，所以后移5位
第二次匹配的话，同理。所以，最后仅仅匹配了2次便查找完毕了，效率很高。
上述案例的运行模式可以见下图：
案例二：T为 HERE IS A SIMPLE EXAMPLE ， P为 EXAMPLE
这个案例取自 BM 算法的创始人之一 Moore 教授自己言传身教的例子。
先来说说什么是好后缀以及好后缀的一些移动规则：
T 和 P 进行匹配的时候，从P 的尾部开始，匹配出的相同的字符串（包括单个字符）即为好后缀，
如 ABCDAB 和 BACD，首次匹配时，首字符对齐，从尾开始匹配，发现有相同的字符串 “CD”，此时的好后缀有 “CD”和“D”，
知道了好后缀的定义，那么根据好后缀计算而得的右移位数的计算方式呢？ 右移位数 = 好后缀的位置 - 好后缀在模式串P中上一次出现的位置。
此处需要注意三点：
① 好后缀的位置，以好后缀的最后一个字符为准，即假设“BACD”的 CD 是好后缀，则好后缀的位置以“D”为准，即4（从1开始计算）；
② 如果好后缀在模式串中只出现过一次，比如：假设“BACD”的 CD 是好后缀，而 CD 仅出现了一次，则上一次出现的位置记做 0（即未出现过）；
③ 如果好后缀有多个，计算上次出现位置时，此时除了最长的那个好后缀，其余的好后缀上次出现的位置必须是在头部（即起始位置）。比如：假设“DCDBACD”的好后缀为 ACD，同样，好后缀还有 CD，D，总共三个好后缀，我们依次来计算上次出现的位置，“ACD”仅出现一次，为0，当没有其它有效的好后缀的时候，便用这个；“CD”上次出现位置不在头部，不计算；“D”这个字符正好和头部相同，故“D”的上次出现位置为1，所以好后缀在模式串P中上一次出现的位置为1。
说完了规则，那么我们正式看案例，见下图：
原理讲明白了，那么我们就该搞清楚其中最为核心的 《坏字符规则表》和《好后缀规则表》 的生成原理了。
五、代码实现
public static void boyerMoore(String pattern, String text) {
int m = pattern.length();
int n = text.length();
Map<String, Integer> bmBc = new HashMap<>();
int[] bmGs = new int[m];
//初始化
preBmBc(pattern, m, bmBc);
preBmGs(pattern, m, bmGs);
//开始匹配
int j = 0;
int i;
int count = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && pattern.charAt(i) == text.charAt(i + j); i--) {
//用于计数
count++;
}
if (i < 0) {
System.out.println("one position is:" + j);
j += bmGs[0];
} else {
j += Math.max(bmGs[i], getBmBc(String.valueOf(text.charAt(i + j)), bmBc, m) - m + 1 + i);
}
}
System.out.println("count:" + count);
}
/**
* 坏字符初始化
*/
private static void preBmBc(String pattern, int patLength, Map<String, Integer> bmBc) {
System.out.println("bmbc start process...");
for (int i = patLength - 2; i >= 0; i--) {
if (!bmBc.containsKey(String.valueOf(pattern.charAt(i)))) {
bmBc.put(String.valueOf(pattern.charAt(i)), patLength - i - 1);
}
}
}
/**
* 好后缀初始化
*/
private static void preBmGs(String pattern, int patLength, int[] bmGs) {
int i, j;
int[] suffix = new int[patLength];
suffix(pattern, patLength, suffix);
//模式串中没有子串匹配上好后缀，也找不到一个最大前缀
for (i = 0; i < patLength; i++) {
bmGs[i] = patLength;
}
//模式串中没有子串匹配上好后缀，但找到一个最大前缀
j = 0;
for (i = patLength - 1; i >= 0; i--) {
if (suffix[i] == i + 1) {
for (; j < patLength - 1 - i; j++) {
if (bmGs[j] == patLength) {
bmGs[j] = patLength - 1 - i;
}
}
}
}
//模式串中有子串匹配上好后缀
for (i = 0; i < patLength - 1; i++) {
bmGs[patLength - 1 - suffix[i]] = patLength - 1 - i;
}
System.out.print("bmGs:");
for (i = 0; i < patLength; i++) {
System.out.print(bmGs[i] + ",");
}
System.out.println();
}
private static void suffix(String pattern, int patLength, int[] suffix) {
suffix[patLength - 1] = patLength;
int q;
for (int i = patLength - 2; i >= 0; i--) {
q = i;
while (q >= 0 && pattern.charAt(q) == pattern.charAt(patLength - 1 - i + q)) {
q--;
}
suffix[i] = i - q;
}
}
private static int getBmBc(String c, Map<String, Integer> bmBc, int m) {
//如果在规则中则返回相应的值，否则返回pattern的长度
return bmBc.getOrDefault(c, m);
}六、资料
1、源码地址：传送门
2、有一篇文章可以参考，很不错，传送门
文章评论