Boyer-Moore算法是一种用于字符串匹配的高效算法，由Robert S. Boyer和J Strother Moore于1977年提出。相比于传统的字符串匹配算法，如朴素的模式匹配算法（Brute-Force）和Knuth-Morris-Pratt算法（KMP），Boyer-Moore算法在某些情况下具有更好的性能。
基本介绍
Boyer-Moore算法的核心思想是根据模式串（要搜索的字符串）的特点，通过预处理生成两个启发式规则：坏字符规则（Bad Character Rule）和好后缀规则（Good Suffix Rule）。这些规则允许我们在匹配过程中跳过尽可能多的不匹配的字符，从而提高匹配效率。
主要步骤：
预处理阶段：
- 坏字符规则（Bad Character Rule）：对于模式串中的每个字符，记录其在模式串中最右边出现的位置。如果在匹配过程中发现坏字符（主串中的字符与模式串中的字符不匹配），根据坏字符规则，将模式串向右滑动尽可能远的距离。
- 好后缀规则（Good Suffix Rule）：对于模式串的每个后缀，找到其与模式串开头匹配的最长前缀。如果在匹配过程中发现好后缀（主串中的一部分与模式串的后缀匹配），根据好后缀规则，将模式串向右滑动尽可能远的距离。
匹配阶段：
-
从主串的开头开始，将模式串与主串逐个字符进行比较。
-
如果匹配成功，继续比较下一个字符。
-
如果匹配失败：
- 根据坏字符规则计算滑动距离，将模式串向右滑动。
- 如果出现好后缀，根据好后缀规则计算滑动距离，将模式串向右滑动。
-
重复上述步骤，直到找到匹配或主串遍历完毕。
Boyer-Moore算法的优势在于，它利用了模式串本身的信息，通过预处理生成启发式规则，能够跳过更多的不匹配字符，减少比较次数，提高匹配效率。尤其在模式串较长、字符集较大的情况下，Boyer-Moore算法的性能优势更为明显。
算法性能
时间复杂度
在最坏情况下，Boyer-Moore算法的时间复杂度为O(n + m)，其中n是主串的长度，m是模式串的长度。这种情况发生在主串和模式串没有任何匹配的字符时，需要对主串中的每个字符都进行比较。然而，通常情况下，Boyer-Moore算法能够通过启发式规则跳过多个字符，从而实现更高效的匹配，使得平均时间复杂度较低。
空间复杂度
Boyer-Moore算法的空间复杂度为O(m)，其中m是模式串的长度。这是因为算法需要存储坏字符规则和好后缀规则的辅助数据结构。具体而言，需要使用两个数组来记录每个字符在模式串中最右边出现的位置，并且还需要一个数组来存储好后缀规则的辅助信息。
需要注意的是，以上给出的时间复杂度和空间复杂度是在预处理阶段完成后进行匹配的情况下的复杂度。如果只进行一次匹配，没有预处理阶段，那么时间复杂度将是O(n * m)，其中n是主串的长度，m是模式串的长度。因此，在单次匹配的情况下，Boyer-Moore算法可能不如其他算法（如KMP算法）高效。
举例分析
以这个字符串为例查找
原字符串：HERE IS A SIMPLE EXAMPLE
查找字符串：EXAMPLE
因为如果尾部字符不匹配，那么只要一次比较，就可以知道前7个字符（整体上）肯定不是要找的结果。
"S"与"E"不匹配。这时， "S"就被称为"坏字符"（bad character），即不匹配的字符。 我们还发现，"S"不包含在搜索词"EXAMPLE"之中，这意味着可以把搜索词直接移到"S"的后一位。
后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置
如果"坏字符"不包含在搜索词之中，则上一次出现位置为 -1。
以"P"为例，它作为"坏字符"，出现在搜索词的第6位（从0开始编号），在搜索词中的上一次出现位置为4，所以后移 6 - 4 = 2位。再以前面第一步的"S"为例，它出现在第6位，上一次出现位置是 -1（即未出现），则整个搜索词后移 6 - (-1) = 7位。
"E"与"E"匹配
比较前面一位，"LE"与"LE"匹配
比较前面一位，"PLE"与"PLE"匹配
比较前面一位，"MPLE"与"MPLE"匹配。
我们把这种情况称为"好后缀"（good suffix），即所有尾部匹配的字符串。 注意，"MPLE"、"PLE"、"LE"、"E"都是好后缀。
接着比较前一位，发现"I"与"A"不匹配。所以，"I"是"坏字符"
根据"坏字符规则"，此时搜索词应该后移 2 - （-1）= 3 位。
问题是，此时有没有更好的移法？
此时存在"好后缀"。所以，可以采用 "好后缀规则" ：
后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置
举例来说，如果字符串"ABCDAB"的后一个"AB"是"好后缀"。那么它的位置是5（从0开始计算，取最后的"B"的值），在"搜索词中的上一次出现位置"是1（第一个"B"的位置），所以后移 5 - 1 = 4位，前一个"AB"移到后一个"AB"的位置。
再举一个例子，如果字符串"ABCDEF"的"EF"是好后缀，则"EF"的位置是5 ，上一次出现的位置是 -1（即未出现），所以后移 5 - (-1) = 6位，即整个字符串移到"F"的后一位。
这个规则有三个注意点：
（1）"好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"EF"是好后缀，则它的位置以"F"为准，即5（从0开始计算）。
（2）如果"好后缀"在搜索词中只出现一次，则它的上一次出现位置为 -1。比如，"EF"在"ABCDEF"之中只出现一次，则它的上一次出现位置为-1（即未出现）。
（3）如果"好后缀"有多个，则除了最长的那个"好后缀"，其他"好后缀"的上一次出现位置必须在头部。比如，假定"BABCDAB"的"好后缀"是"DAB"、"AB"、"B"，请问这时"好后缀"的上一次出现位置是什么？回答是，此时采用的好后缀是"B"，它的上一次出现位置是头部，即第0位。这个规则也可以这样表达：如果最长的那个"好后缀"只出现一次，则可以把搜索词改写成如下形式进行位置计算"(DA)BABCDAB"，即虚拟加入最前面的"DA"。
回到上文的这个例子。此时，所有的"好后缀"（MPLE、PLE、LE、E）之中，只有"E"在"EXAMPLE"还出现在头部，所以后移 6 - 0 = 6位。
可以看到，"坏字符规则"只能移3位，"好后缀规则"可以移6位。所以，Boyer-Moore算法的基本思想是，每次后移这两个规则之中的较大值。
更巧妙的是，这两个规则的移动位数，只与搜索词有关，与原字符串无关。因此，可以预先计算生成《坏字符规则表》和《好后缀规则表》。使用时，只要查表比较一下就可以了。
继续从尾部开始比较，"P"与"E"不匹配，因此"P"是"坏字符"。根据"坏字符规则"，后移 6 - 4 = 2位。
从尾部开始逐位比较，发现全部匹配，于是搜索结束。如果还要继续查找（即找出全部匹配），则根据"好后缀规则"，后移 6 - 0 = 6位，即头部的"E"移到尾部的"E"的位置。
JAVA实现
按照上述思路实现的JAVA代码
public class BoyerMooreTest {
private static int ALPHABET_SIZE = 256;
private static int max(int a, int b) {
return (a > b) ? a : b;
}
private static int[] generateBadCharHeuristic(char[] pattern) {
int patternLength = pattern.length;
int[] badChar = new int[ALPHABET_SIZE];
for (int i = 0; i < ALPHABET_SIZE; i++) {
badChar[i] = -1;
}
for (int i = 0; i = 0; i--) {
if (isPrefix(pattern, i + 1)) {
lastPrefixPosition = i + 1;
}
suffix[i] = lastPrefixPosition - i + patternLength - 1;
}
for (int i = 0; i < patternLength - 1; i++) {
int suffixLength = getSuffixLength(pattern, i -1);
if (pattern[i - suffixLength] != pattern[patternLength - 1 - suffixLength]) {
goodSuffix[suffixLength] = patternLength - 1 - i + suffixLength;
}
}
for (int i = 0; i < patternLength - 1; i++) {
goodSuffix[i] = goodSuffix[i + 1];
}
return goodSuffix;
}
private static boolean isPrefix(char[] pattern, int p) {
int patternLength = pattern.length;
for (int i = p, j = 0; i = 0 && pattern[i] == pattern[j]; i--, j--) {
len++;
}
return len;
}
public static List search(String text, String pattern) {
List matches = new ArrayList();
char[] textArray = text.toCharArray();
char[] patternArray = pattern.toCharArray();
int textLength = text.length();
int patternLength = pattern.length();
int[] badChar = generateBadCharHeuristic(patternArray);
int[] goodSuffix = generateGoodSuffixHeuristic(patternArray);
int shift = 0;
while (shift = 0 && patternArray[j] == textArray[shift + j]) {
j--;
}
if (j < 0) {
matches.add(shift);
shift += goodSuffix[0];
} else {
int badCharShift = j - badChar[textArray[shift + j]];
int goodSuffixShift = goodSuffix[j];
shift += max(badCharShift, goodSuffixShift);
}
}
return matches;
}
@Test
public void testBoyerMoore() {
String text = "HERE IS A AAA EXAMPLEXAMPLE SIMPLE EXAMPLE";
String pattern = "EXAMPLE";
List matches = search(text, pattern);
if (matches.isEmpty()) {
System.out.println("No matches found.");
} else {
System.out.println("Matches found at indices:");
for (int index : matches) {
System.out.println(index);
}
}
}
}
最终运行结果如下
Matches found at indices:
14
20
35
参考
1.字符串匹配 - Boyer–Moore 算法原理和实现
