[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.