上一节所介绍的KMP算法 计算时间在最坏情况下也可以保证不超过线性 这的确是一个好消息 然而 倘若我们因此就停下继续优化的脚步 那就大错特错了 实际上 串匹配问题与一般的搜索问题的确有着本质的区别 在我们此前所讨论的所有搜索算法中 每次比对 都是一种一对一的模式 也就是一个目标 与另一个候选者 判定二者是否相等 的确只需常数的时间 而现在 虽然基本的数据对象是单个的字符 而所谓的串匹配 则是相对于由若干个字符在局部组成的一个片段而言的 也就是说 是由多个字符对多个字符 二者匹配 当且仅当每一对字符彼此相等 然而需要特别注意的是 反过来 一旦发现有一对字符不等 我们就立即可以判断串失配 由此可见 从计算成本的角度来看 判定一对串是否相等 与判定它们是否不等 并不是完全一样的 我们接下来将要介绍的BM算法 就充分地利用了这一性质 从而使得串匹配的效率得以进一步地提高 实际上 这一算法同时采用了两种策略 在接下来的这一节 我们首先来讨论所谓的坏字符策略