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

Question

题目中已经有问题了，Python中str.find(string, substring)的C实现的最坏情况时间复杂度是多少 if n是string的长度，m是substring的长度？源代码 ( https://hg.python.org/cpython/file/99f5a0475ead/Objects/stringlib/fastsearch.h ) 似乎在谈论 boyer-moore-horspool 算法，根据维基百科，该算法的最坏情况复杂度为 O(m*n ).

编辑: O(m*n) 是指 boyer-moore- 的运行时间horspool 算法，查找字符串中出现的所有 个子字符串。 Python 的 str.find 方法只找到子字符串的 one 出现，所以它的 (str.find) 将取决于在 substring 第一次出现的位置。所以不，我还没有发布答案。

Answer 1

The source code seems to talk about the boyer-moore-horspool algorithm, which according to Wikipedia has a worst-case complexity of O(m*n).

对于 CPython，您的答案是 O(m*n)。一般来说，它显然依赖于实现。

编辑:是的，如果您已经进行了研究，我想知道您为什么要问这个问题。