Worst time complexity of str.find in python
The question is already in the title, what is the worst time complexity of a C implementation str.find(string, substring)
in Python if n is length string
and m is length substring
? The original code ( https://hg.python.org/cpython/file/99f5a0475ead/Objects/stringlib/fastsearch.h ) seems to speak of the boyer-moore-horspool algorithm, which according to Wikipedia has the worst complexity O (t * P).
EDIT: o (m * n) refers to the runtime of the Boyer-moore-horspool algorithm, which finds all occurrences of a substring in a string.The Python method str.find
only detects one occurrence of a substring, so it ( str.find
) will depend on the position of the first occurrence substring
. So NO, I haven't posted an answer yet.
source to share
The original code seems to be talking about the boyer-moore-horspool algorithm, which according to Wikipedia has the worst O (m * n) complexity.
Your answer O(m*n)
for CPython. In general, it is clearly implementation dependent.
EDIT: Yes, I was wondering why you are asking this if you have already done your research.
source to share