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

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