25 字符串匹配之 BM 算法
最优匹配的 BM 算法
1. BM 算法
本节我们继续介绍另一个高效的字符串匹配算法 BM(Boyer-Moore)。BM 与 KMP 优化思路类似，都是希望尽可能增加发生不匹配时，模式串后移的位数来提高字符串的匹配效率。BM 要想达到更高的匹配效率，必需利用更多的已知信息。
这里依旧推荐阮一峰老师有关 BM算法的博客。因为阮一峰老师讲的已经不能在通俗易懂，这里我就简单总结一下 BM 算法所使用的匹配规则。示例采用博客中的示例，即在"HERE IS A SIMPLE EXAMPLE"，中搜索 “EXAMPLE”。
1.1 坏字符规则
开始匹配时，主串与模式串头部对齐，从尾部开始比较。此时"S"与"E"不匹配。我们称"S"为"坏字符"（bad character），即不匹配的字符。
利用坏字符以及坏字符是否出现在模式串中，BR 算法使用的第一个移位规则被称为坏字符规则: 后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置。如果"坏字符"不包含在搜索词之中，则上一次出现位置为 -1。道理很显而易见，如果出现坏字符，我们就直接把模式串移动到能跟坏字符匹配的位置上来。
示例中"S"不包含在搜索词"EXAMPLE"之中，这意味着可以把搜索词直接移到"S"的后一位
1.2 好后缀规则
借鉴 KMP 算法，利用已经匹配的字符串和已匹配部分是否出现在模式串中，BR 算法使用的第二个移位规则被称为 好后缀规则:后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置
- “好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"EF"是好后缀，则它的位置以"F"为准，即5（从0开始计算）。
- 如果"好后缀"在搜索词中只出现一次，则它的上一次出现位置为 -1。比如，“EF"在"ABCDEF"之中只出现一次，则它的上一次出现位置为-1（即未出现）。
- 如果"好后缀"有多个，则除了最长的那个"好后缀”，其他"好后缀"的上一次出现位置必须在头部。比如，假定"BABCDAB"的"好后缀"是"DAB”、“AB”、“B”，请问这时"好后缀"的上一次出现位置是什么？回答是，此时采用的好后缀是"B"，它的上一次出现位置是头部，即第0位
道理也很显而易见，如果已经匹配的部分多次出现在模式串，当发生不匹配时，就直接把模式串移动到上一次匹配的位置上。显然 BM 与KMP 不同，BM 不要求后缀匹配的部分必需是模式串的前缀。
“MPLE"与"MPLE"匹配。我们把这种情况称为"好后缀”（good suffix），即所有尾部匹配的字符串。注意，“MPLE”、“PLE”、“LE”、“E"都是好后缀。此时，所有的"好后缀”（MPLE、PLE、LE、E）之中，只有"E"在"EXAMPLE"还出现在头部，所以后移 6 - 0 = 6位。
1.3 移位选择
Boyer-Moore算法的基本思想是，每次后移这两个规则之中的较大值。更巧妙的是，这两个规则的移动位数，只与模式串有关，与主串无关。因此，可以预先计算生成《坏字符规则表》和《好后缀规则表》。使用时，只要查表比较一下就可以了。
2. 实现
显然 BR 算法的核心是要先生成《坏字符规则表》和《好后缀规则表》，然后利用这两个规则表进行字符串匹配。
2.1 坏字符规则表
2.2 好后缀规则表
2.3 字符串匹配
参考: