大话数据结构十二：字符串的模式匹配（BM算法）

1. BM算法简介：

KMP算法其实并不是效率最高的字符串匹配算法，实际应用的并不多，各种文本编辑器的“查找”功能大多采用的是BM算法(Boyer Moore)。BM算法效率更高，更容易理解。

2. BM算法分析：

（1） 假定字符串为"HERE IS A SIMPLE EXAMPLE"，搜索词为"EXAMPLE"。

（2） 首先，"字符串"与"搜索词"头部对齐，从尾部开始比较。这是一个很聪明的想法，因为如果尾部字符不匹配，那么只要一次比较，就可以知道前7个字符（整体上）肯定不是要找的结果。我们看到，"S"与"E"不匹配。这时，"S"就被称为"坏字符"（bad character），即不匹配的字符。我们还发现，"S"不包含在搜索词"EXAMPLE"之中，这意味着可以把搜索词直接移到"S"的后一位。

（3） 依然从尾部开始比较，发现"P"与"E"不匹配，所以"P"是"坏字符"。但是，"P"包含在搜索词"EXAMPLE"之中。所以，将搜索词后移两位，两个"P"对齐。

（4） 我们由此总结出"坏字符规则"：

后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置值

如果"坏字符"不包含在搜索词之中，则上一次出现位置为 -1。

以"P"为例，它作为"坏字符"，出现在搜索词的第6位（从0开始编号），在搜索词中的上一次出现位置为4，所以后移 6 - 4 = 2位。再以前面第二步的"S"为例，它出现在第6位，上一次出现位置是 -1（即未出现），则整个搜索词后移 6 - (-1) = 7位。

（5） 依然从尾部开始比较，"E"与"E"匹配。

（6） 比较前面一位，"LE"与"LE"匹配。