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

Question

在Boyer-Moore字符串搜索算法wiki链接中，Boyer-Moore的最坏情况复杂性是

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

但在字符串搜索算法wiki中，我们指出Boyer的最坏情况复杂性是O(n).为何会有这样的差距呢？

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

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

Answer 1

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

预处理为Θ(m + k) + O(n)进行匹配。