BM 算法
收录于
学习数据结构与算法
2022-08-27 18:47 · 阅读时长10分钟
BM 算法是一种改进的字符串匹配算法，由 Bob Boyer 和 J Strother Moore 提出，该算法被认为最高效的字符串匹配算法，常用于文本编辑器中的搜索匹配功能，比如大家所熟知的 GNU grep 命令使用的就是该算法。
算法特点
BM 算法和KMP 算法的匹配顺序不一样，它是从模式串的右边往左开始比较，而且它有两种跳跃匹配规则，一种叫 “坏字符规则”，另外一种叫 “好后缀规则”，在匹配过程中取两者中的最大值进行跳跃。
坏字符规则
坏字符指的是在某一轮匹配过程中，字符串中第一个无法匹配的字符。比如：
在这轮比较中，‘d’ 这个字符就是坏字符。对于坏字符，有两种情况。
1、坏字符在模式串中不存在
也就是上面示例这种情况，对于这种情况，直接将整个模式串跳过坏字符，然后开始比较，如下：
2、坏字符在模式串中存在
比如这个示例：
对于这种情况，我们需要将模式串中最后一个坏字符出现的位置与匹配失败的位置对齐，然后继续比较，如下：
好后缀规则
好后缀指的是在某一轮匹配过程中，匹配失败之前已匹配成功的子串。比如：
在这轮比较中，子串 “ab” 就是好后缀。对于好后缀，有三种情况。
1、模式串中存在和好后缀相同的子串
也就是上面这个示例的情况，对于这种情况，我们需要将模式串中（除好后缀本身以外）最后一个与好后缀相同的子串与好后缀对齐，然后继续比较，如下：
2、模式串中存在某个前缀和好后缀的某个后缀相同
这种情况需要将模式串和好后缀中最长的相同前后缀对齐，然后继续比较，比如这个示例：
在这示例中好后缀是 “cab”，而模式串的前缀 “ab” 正好和好后缀的后缀 “ab” 相同，这种情况需要将这个相同的前后缀对齐，然后继续比较。如下：
3、模式串中即不存在与好后缀相同的子串也不存在某个前缀和好后缀的某个后缀相同
比如这个示例：
对于这种情况，只需要将整个模式串跳过好后缀，然后继续比较，如下：
算法实现
1public int indexOf(String text, String pattern) {
2 if ("".equals(pattern)) {
3 return 0;
4 }
5 Map<Character, Integer> badTable = createBadTable(pattern);
6 int[] goodTable = createGoodTable(pattern);
7 int i = pattern.length() - 1;
8 while (i < text.length()) {
9 int j = pattern.length() - 1;
10 while (pattern.charAt(j) == text.charAt(i)) {
11 if (j == 0) {
12 return i;
13 }
14 i--;
15 j--;
16 }
17 /**
18 * 模式串不存在坏字符则让整个模式串跳过
19 */
20 int badSkip = badTable.getOrDefault(text.charAt(i), pattern.length());
21 /**
22 * 取坏字符规则和好后缀规则较大的步长
23 */
24 i += Math.max(goodTable[j], badSkip);
25 }
26 return -1;
27}
28
29/**
30 * 保存在模式串中存在的坏字符的跳跃步长表
31 * 跳跃步长 = 模式串中最后一个坏字符的位置到模式串结尾的长度
32 * @param pattern
33 * @return
34 */
35public Map<Character, Integer> createBadTable(String pattern) {
36 Map<Character, Integer> table = new HashMap<>();
37 for (int i = 0; i < pattern.length(); i++) {
38 table.put(pattern.charAt(i), pattern.length() - 1 - i);
39 }
40 return table;
41}
42
43/**
44 * table保存好后缀的跳跃步长
45 *
46 * @param pattern
47 * @return
48 */
49public int[] createGoodTable(String pattern) {
50 int[] table = new int[pattern.length()];
51
52 /**
53 * 第三种情况：模式串中即不存在与好后缀相同的子串也不存在某个前缀和好后缀的某个后缀相同
54 * 直接将整个模式串跳过好后缀。
55 * 跳跃步长 = 当前已匹配长度（或者好后缀的长度） + 模式串长度
56 */
57 for (int i = 0; i < pattern.length(); i++) {
58 table[i] = pattern.length() + pattern.length() - 1 - i;
59 }
60
61 /**
62 * 辅助数组，第i个元素保存的是模式串中以第i个元素结尾的子串和模式串中最长相同后缀的长度
63 */
64 int[] suffix = new int[pattern.length()];
65 for (int i = 0; i < suffix.length; i++) {
66 int j = i, k = pattern.length() - 1;
67 while (j >= 0 && pattern.charAt(j) == pattern.charAt(k)) {
68 j--;
69 k--;
70 }
71 suffix[i] = i - j;
72 }
73
74 /**
75 * 第二种情况：模式串中存在某个前缀和好后缀的某个后缀相同
76 * 需要将模式串和好后缀中最长的相同前后缀对齐
77 *
78 */
79 for (int i = 0; i < pattern.length(); i++) {
80 if (suffix[i] != i + 1) {
81 continue;
82 }
83 /**
84 * suffix[i] == i + 1，说明pattern[0, i]既是模式串的前缀也是模式串的后缀
85 * 也就是说pattern[0, i]和pattern[pattern.length() - 1 - i, pattern.length() - 1]是相同的
86 * 计算所有长度大于等于i + 1的好后缀的跳跃步长
87 * 跳跃步长 = 当前已匹配长度（或者好后缀的长度） + 模式串长度 - 相同前后缀的长度
88 */
89 for (int j = 0; j < pattern.length() - 1 - i; j++) {
90 table[j] = pattern.length() + pattern.length() - 1 - j - suffix[i];
91 }
92 }
93
94 /**
95 * 第一种情况：模式串中存在和好后缀相同的子串
96 * 需要将模式串中（除好后缀本身以外）最后一个与好后缀相同的子串与好后缀对齐
97 * 跳跃步长 = 与好后缀相同的子串的结尾位置到模式串结尾的长度 + 当前已匹配长度（或者好后缀的长度）
98 */
99 for (int i = 0; i < pattern.length() - 1; i++) {
100 table[pattern.length() - 1 - suffix[i]] = pattern.length() - 1 - i + suffix[i];
101 }
102 return table;
103}补充：只有坏字符规则的算法实现
1public int indexOf(String text, String pattern) {
2 if ("".equals(pattern)) {
3 return 0;
4 }
5 Map<Character, Integer> badTable = createBadTable(pattern);
6 int i = pattern.length() - 1;
7 while (i < text.length()) {
8 int j = pattern.length() - 1;
9 /**
10 * 只坏字符规则可能往后走，所以记录下一个匹配开始的位置，如果坏字符匹配结果往后走，则直接跳转到下一个位置
11 */
12 int defaultNext = i + 1;
13 while (pattern.charAt(j) == text.charAt(i)) {
14 if (j == 0) {
15 return i;
16 }
17 i--;
18 j--;
19 }
20 /**
21 * 模式串不存在坏字符则让整个模式串跳过
22 */
23 int badSkip = badTable.getOrDefault(text.charAt(i), pattern.length());
24 /**
25 * 取坏字符规则和好后缀规则较大的步长
26 */
27 i += Math.max(defaultNext - i, badSkip);
28 }
29 return -1;
30}
31
32/**
33 * 保存在模式串中存在的坏字符的跳跃步长表
34 * 跳跃步长 = 模式串中最后一个坏字符的位置到模式串结尾的长度
35 * @param pattern
36 * @return
37 */
38public Map<Character, Integer> createBadTable(String pattern) {
39 Map<Character, Integer> table = new HashMap<>();
40 for (int i = 0; i < pattern.length(); i++) {
41 table.put(pattern.charAt(i), pattern.length() - 1 - i);
42 }
43 return table;
44}BM算法字符串匹配
上一篇
KMP 算法
1