哪种字符串搜索算法更好？Boyer-Moore还是Boyer Moore Horspool？

Question

Boyer - Moore算法的预处理时间为Θ(m + |Σ|)，匹配时间为Ω(n/m)，O(n)。我知道Boyer Moore Horspool是简化Boyer Moore本身的改进，但是根据this Wikipedia article的说法，它的平均情况复杂度是O(N)和最坏情况O(MN)。因此，在最坏的情况下，它应该比Boyer Moore算法慢。但智利大学的this classic survey显示，博耶-摩尔horspool几乎每次都优于博耶·摩尔。我很困惑！我应该使用哪种算法(对于小模式和大模式)进行字符串搜索，哪种算法在实际世界中更有意义(我只是一名计算机科学专业的学生)？

Answer 1

关键词是“几乎”。最坏的情况可能发生在极少数的情况下。现实生活中的平均行为和渐近行为也是相当松散耦合的。Boyer-Moore-Horspool的最佳情况行为与Boyer-Moore的情况相同。对Boyer-Moore-Horspool来说，最坏的情况比Boyer-Moore要糟糕得多。对于典型应用，Boyer-Moore-Horspool倾向于与Boyer-Moore大致相同，但具有更好(更低)的开销和初始化成本。

使用哪一个？这取决于您的目标以及您对要搜索的模式和文本的期望。两者都不是特别难实现，所以为什么不同时实现这两种方法，并自己比较结果。(看到当你承认自己是一个学生时会发生什么吗？你得到了一个任务！:))