[Python-Dev] string find(substring) vs. substring in string
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 :)
> Python-Dev mailing list
> Python-Dev at python.org
> Unsubscribe: http://mail.python.org/mailman/options/python-dev/allison%40sumeru.stanford.edu
More information about the Python-Dev