worstcase时间复杂度str.查找在python中

Question

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

编辑：O（m*n）是指boyer-moore-horsool算法的运行时间，该算法会发现所有字符串中出现的子串。Python的str.find方法只找到子串的一个出现，因此它（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)。一般来说，它显然依赖于实现。在

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