Python - search function ()

Question

I am looking for an effective way to check if a short string is a long string. I saw several suggestions on this topic: Python is an effective way to check if a very large string contains a substring

However, I have not seen the use of find () there. Is it useful to use the find () function? What is the time complexity?

I looked at the Wiki page but did not find find (). https://wiki.python.org/moin/TimeComplexity

Answer 1

Quickly looking at the source, it seems that it str.findis calling stringlib_find_slicefrom here , which ultimately calls fastsearch. The actual algorithm is explained here - with the python pseudocode (which I got from reading the comments).

It looks like the worst case implementation is O (N * M) (same as the naive approach), but can do O (N / M) in some cases (where N and M are the lengths of the string and substring, respectively) and O (N ) in frequent cases ¹ .

^{1 (do not quote me on it - I was only looking at the document)}