Dhruv Matani wrote:
>> all the complexity figures of the Boyer-Moore algorithm are not valid
>> anymore.
>
> No, we don't want to do that. Because using a map like that means that
>
> Yes, you are kind of right, but not entirely. The complexity remains
> the same. It's just that the constants in the big oh notation get
> blown out of proportion because of the lookup times in the hash maps.
No, at minimum we have to start talking about *average* complexity,
instead of plain complexity as in the real BM algorithm. And of course,
in practice, the constants are plain horrible...
>> Therefore, either we find a better way to deal with that
>> problem (I suggest we don't give up so quickly, no reason to rush) or we
>> have to deliver the algorithm only for chars.
>
> I'm not ruling out any possibilities, but in all fairness, I think the
> Boyer-Moore(and other string matching) algorithms rely on the fact
> that these tables could be created and looked up fairly
> quickly(comparable to character compare time)
Certainly.