string - Boyer-Moore 字符串搜索算法运行时间复杂度

Question

在Boyer-Moore 字符串搜索算法 wiki链接中，声明 Boyer-Moore 的最坏情况复杂度为

1. O(m+n)如果模式没有出现在文本中
2. O(mn)如果模式确实出现在文本中

但是在String Search Algorithm wiki中，据说 Boyer-Moore 的最坏情况复杂度是O(n)。为什么会出现这种差距？

在最坏的情况下，这里也被称为 O(mn)。

那么 Boyer-Moore 算法的正确运行时间复杂度是多少？

Answer 1

差异来自不同的定义。在一般的字符串搜索页面中，算法的复杂性分为预处理和匹配，而算法本身的页面并没有做出这种区分。

预处理将是 Θ(m + k) 加上 O(n) 进行匹配。