BM 算法

BM 算法是一种改进的字符串匹配算法，由 Bob Boyer 和 J Strother Moore 提出，该算法被认为最高效的字符串匹配算法，常用于文本编辑器中的搜索匹配功能，比如大家所熟知的 GNU grep 命令使用的就是该算法。

算法特点

BM 算法和KMP 算法的匹配顺序不一样，它是从模式串的右边往左开始比较，而且它有两种跳跃匹配规则，一种叫 “坏字符规则”，另外一种叫 “好后缀规则”，在匹配过程中取两者中的最大值进行跳跃。

坏字符规则

坏字符指的是在某一轮匹配过程中，字符串中第一个无法匹配的字符。比如：

在这轮比较中，‘d’ 这个字符就是坏字符。对于坏字符，有两种情况。

1、坏字符在模式串中不存在

也就是上面示例这种情况，对于这种情况，直接将整个模式串跳过坏字符，然后开始比较，如下：

2、坏字符在模式串中存在

比如这个示例：

对于这种情况，我们需要将模式串中最后一个坏字符出现的位置与匹配失败的位置对齐，然后继续比较，如下：

好后缀规则

好后缀指的是在某一轮匹配过程中，匹配失败之前已匹配成功的子串。比如：

在这轮比较中，子串 “ab” 就是好后缀。对于好后缀，有三种情况。

1、模式串中存在和好后缀相同的子串

也就是上面这个示例的情况，对于这种情况，我们需要将模式串中（除好后缀本身以外）最后一个与好后缀相同的子串与好后缀对齐，然后继续比较，如下：

2、模式串中存在某个前缀和好后缀的某个后缀相同

这种情况需要将模式串和好后缀中最长的相同前后缀对齐，然后继续比较，比如这个示例：

在这示例中好后缀是 “cab”，而模式串的前缀 “ab” 正好和好后缀的后缀 “ab” 相同，这种情况需要将这个相同的前后缀对齐，然后继续比较。如下：

3、模式串中即不存在与好后缀相同的子串也不存在某个前缀和好后缀的某个后缀相同

比如这个示例：

对于这种情况，只需要将整个模式串跳过好后缀，然后继续比较，如下：

算法实现

补充：只有坏字符规则的算法实现