[Python-Dev] string find(substring) vs. substring in string

Dennis Allison allison at sumeru.stanford.EDU
Thu Feb 17 01:06:24 CET 2005

Boyer-Moore and variants need a bit of preprocessing on the pattern which
makes them great for long patterns but more costly for short ones.

On Wed, 16 Feb 2005, Irmen de Jong wrote:

> Mike Brown wrote:
> > Fredrik Lundh wrote:
> > 
> >>any special reason why "in" is faster if the substring is found, but
> >>a lot slower if it's not in there?
> > 
> > 
> > Just guessing here, but in general I would think that it would stop searching 
> > as soon as it found it, whereas until then, it keeps looking, which takes more 
> > time. But I would also hope that it would be smart enough to know that it 
> > doesn't need to look past the 2nd character in 'not the xyz' when it is 
> > searching for 'not there' (due to the lengths of the sequences).
> There's the Boyer-Moore string search algorithm which is
> allegedly much faster than a simplistic scanning approach,
> and I also found this: http://portal.acm.org/citation.cfm?id=79184
> So perhaps there's room for improvement :)
> --Irmen
> _______________________________________________
> Python-Dev mailing list
> Python-Dev at python.org
> http://mail.python.org/mailman/listinfo/python-dev
> Unsubscribe: http://mail.python.org/mailman/options/python-dev/allison%40sumeru.stanford.edu

More information about the Python-Dev mailing list