[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: freshman-level Boyer-Moore fast string search

On 7/29/05, Alex Shinn <alexshinn@xxxxxxxxx> wrote:
> Is the three-stage assumption for binary trees?  That would suggest
> the search strings are never longer than 8 characters.  In practice I
> frequently search for much longer strings - "call-with-current-continuation"
> at 30 characters (5 stage lookup) is fairly common, and mult-line
> searches are not unheard of.  You can't just dismiss a lg(m) factor.

Oops, that was careless.  The real cost depth is proportional to the
log of the number of distinct characters, 13 distinct characters for
call-with-current-continuation for a 4 stage lookup.