Re: the lowest number of comparisons in string matching

laura <laura.brandusan@xxxxxxxxx> wrote:

Hi,

Which is the number of comparisons in the worst case?

I'm not actually certain what the exact bound is, but I do believe that
one needs at least n character comparisons in the worst case to check
whether a pattern occurs in a text. (This includes any preprocessing
done on the pattern.)

Tor Myklebust
.