CODEWITHSUNDEEP
pythoncstringalgorithmtime-complexity
0x539
0x539

Reputation: 1496

worst-case time complexity of str.find in python

The question is already in the title, what is the worst-case time complexity of the C implementation of str.find(string, substring) in Python if n is the length of string and m is the length of substring? The source code (https://hg.python.org/cpython/file/99f5a0475ead/Objects/stringlib/fastsearch.h) seems to talk about the boyer-moore-horspool algorithm, which according to Wikipedia has a worst-case complexity of O(m*n).

EDIT: O(m*n) refers to the runnning time of the boyer-moore-horspool Algorithm, which finds all the occurrences of a substring in a string. Python's str.find Method finds only one occurrence of the substring, so it's (str.find) will depend on the position of the first occurrence of substring. So NO, I haven't already posted the answer.

Upvotes: 11

Views: 8242

Answers (1)

Marcus Müller
Marcus Müller

Reputation: 36462

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).

The answer is O(m*n) for CPython. In general, it's obviously implementation-dependent.

EDIT: Yes, I wondered why you're asking this, if you'd already done the research.

Upvotes: 3

Related Questions