I am thinking of how the in
operator implement, for instance
>>> s1 = 'abcdef'
>>> s2 = 'bcd'
>>> s2 in s1
True
In CPython, which algorithm is used to implement the string match, and what is the time complexity? Is there any official document or wiki about this?
It's a combination of Boyer-Moore and Horspool.
You can view the C code here:
Fast search/count implementation, based on a mix between Boyer-Moore and Horspool, with a few more bells and whistles on the top. For some more background, see: http://effbot.org/zone/stringlib.htm.
From the link above:
When designing the new algorithm, I used the following constraints: