为什么在文本编辑器的查找函数中选择“BM算法”而不是“周日算法”?

正如你可能从名字中猜到的那样,周日的Boyer Moore Horspool变体与Boyer Moore非常相似。

支持Boyer-Moore的论点是,虽然代码更复杂,但它将搜索所需的比较次数减少到接近绝对必要的最小值。最大的问题是,这需要更多的预处理(和更多的内存)。

就我而言,

全vertion-Boyer-Moore算法通过两个表加快字符串匹配: delta1 delta2 也被称为 .

三角洲1 三角洲2 工作时间超过 三角洲1

对于delta2,需要一些复杂的预处理(如果写入时间复杂度为O(n)代码) 和更多的内存(它持有一个额外的字母表),简化的Boyer-Moore算法只需使用 桌子它在常见情况下运行良好。

文本编辑器不关心更多的内存负载(最多256字节),完整版本的Boyer-Moore算法是更合理的选择。