[Python-Dev] Re: string find(substring) vs. substring in string (original) (raw)

Fredrik Lundh fredrik at pythonware.com
Thu Feb 17 00:10:29 CET 2005

Scott David Daniels wrote:

Looking for "not there" in "not the xyz"*100 using Boyer-Moore should do about 300 probes once the table is set (the underscores below):

not the xyznot the xyznot the xyz... not ther not the_ not ther not the_ not ther ...

yup; it gets into a 9/2/9/2 rut. tweak the pattern a little, and you get better results for BM.

("kill" is of course an understatement, but BM usually works better. but it still needs a sizeof(alphabet) table, so you can pretty much forget about it if you want to support unicode...)

More information about the Python-Dev mailing list