Boyer Moore 算法的预处理时间为 Θ(m + |Σ|)，匹配时间为 Ω(n/m)，O(n)。我知道 Boyer Moore Horspool 是 Simplified Boyer Moore 本身的一个进步，但是根据这篇 Wikipedia 文章，它的平均情况复杂度是 O(N) 和最坏情况 O(MN) 。所以在最坏的情况下，它应该比 Boyer Moore 算法慢。但智利大学的这项经典调查显示，Boyer-Moore horspool 几乎每次都优于 Boyer Moore。我很困惑！我应该使用哪个（对于小型和大型模式）进行字符串搜索，哪种算法在实际世界中具有更大的意义（我只是一名计算机科学专业的学生）？
问问题
2137 次
1 回答
4
关键词是“几乎”。最坏情况的行为可能是极少数情况。现实生活中的平均行为和渐近行为也是相当松散耦合的。Boyer-Moore-Horspool的最佳情况行为与 Boyer-Moore 相同。Boyer-Moore-Horspool 的最坏情况比 Boyer-Moore 更糟糕。对于典型使用，Boyer-Moore-Horspool 往往与 Boyer-Moore 大致相同，但开销和初始化成本稍好（较低）。
使用哪一个？这取决于您的目标以及您对要搜索的模式和文本的期望。两者都不是特别难以实施，所以为什么不两者都做并自己比较结果。（看看当你承认自己是学生时会发生什么？你得到了作业！:)）
于 2012-07-12T23:35:28.733 回答