python 中 str.find 的最坏情况时间复杂度

Question

问题已经在标题中了，如果

n

是str.find(string, substring)的长度，

m

是string的长度，那么Python中

substring

的C实现的最坏情况时间复杂度是多少？源代码（https://hg.python.org/cpython/file/99f5a0475ead/Objects/stringlib/fastsearch.h）似乎在谈论 boyer-moore-horspool 算法，根据维基百科，该算法有一个最差的 -情况复杂度为 O(m*n)。

编辑： O(m*n) 指的是 boyer-moore-horspool 算法的运行时间，该算法查找字符串中子字符串的 all 的出现。 Python 的

str.find

方法只能查找 一次 出现的子字符串，因此它的 (

str.find

) 将取决于

substring

第一次出现的位置。所以不，我还没有发布答案。

Answer 1

源代码似乎谈论的是 boyer-moore-horspool 算法，根据维基百科，该算法的最坏情况复杂度为 O(m*n)。

对于 CPython，答案是

O(m*n)

。一般来说，这显然取决于实现。

编辑：是的，我想知道你为什么问这个，如果你已经完成了研究。