434,960 Members | 2,324 Online
Need help? Post your question and get tips & solutions from a community of 434,960 IT Pros & Developers. It's quick & easy.

# What algorithm does Python use to evaluate: if substring in string

 P: n/a I would be surprised if it is the naive: m = 0 s1 = "me" s2 = "locate me" s1len = len(s1) s2len = len(s2) found = False while m + s1len <= s2len: if s1 == s2len[m:m+s1len]: found = True break m += 1 Sep 9 '06 #1
5 Replies

 P: n/a Tor Erik

 P: n/a In , Tor Erik wrote: I would be surprised if it is the naive: Why? I guess it simply calls an appropriate C library function. Ciao, Marc 'BlackJack' Rintsch Sep 9 '06 #3

 P: n/a Alex Martelli wrote: Tor Erik I would be surprised if it is the naive: Yep -- it's "a mix between Boyer-Moore and Horspool with a few more bells and whistles on the top", as documented and implemented in Objects/stringlib/fastsearch.h in the Python sources and well discussed and explained at http://effbot.org/zone/stringlib.htm . Alex Ok. Two questions: 1. Is "a in b" simply an alias for "b.find(a)"? 2. Is this algorithm exclusive to Python 2.5, or is it contained in 2.4 aswell? Sep 9 '06 #4

 P: n/a Tor Erik

 P: n/a "Tor Erik" wrote: I would be surprised if it is the naive: 2.4 and earlier uses that algorithm (but with a better implementation). And "naive" isn't really the right word here; on average, a brute force search is pretty good for the find/index/in use case. Most fancy algorithms ignore the setup costs and other overhead, which works well in theory, but not that well in practice. Sep 11 '06 #6

### This discussion thread is closed

Replies have been disabled for this discussion.