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

Question

问题已经在标题中，str.find(string, substring)如果n是的长度，string而m是的长度，那么Python中C实现的最坏情况下的时间复杂度是substring多少？源代码（https://hg.python.org/cpython/file/99f5a0475ead/Objects/stringlib/fastsearch.h）似乎在谈论boyer-moore-horspool算法，根据Wikipedia的说法，这种算法的复杂性最差O（m * n）的

编辑： O（ m * n）指的是博耶·摩尔·霍尔斯普尔算法的运行时间，该算法查找字符串中所有出现的子字符串。Python的str.findMethod仅找到子字符串的一个实例，因此它的（str.find）将取决于第一次出现的位置substring。所以不，我还没有发布答案。

Answer 1

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

你的答案是O(m*n)CPython。一般来说，它显然取决于实现。

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