Search code examples
pythontime-complexitypython-internals

Runtime of python's if substring in string

What is the big O of the following if statement?

if "pl" in "apple":
   ...

What is the overall big O of how python determines if the string "pl" is found in the string "apple"

or any other substring in string search.

Is this the most efficient way to test if a substring is in a string? Does it use the same algorithm as .find()?

Solution

  • In Python 3.4.2, it looks like they are resorting to the same function, but there may be a difference in timing nevertheless. For example, s.find first is required to look up the find method of the string and such.

    The algorithm used is a mix between Boyer-More and Horspool.