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@python.org > http://mail.python.org/mailman/listinfo/python-dev > Unsubscribe: > http://mail.python.org/mailman/options/python-dev/allison%40sumeru.stanford.edu > _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com