Re: text_position worst case runtime

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> If it did that might be a nice solution, but I'm not sure that it does
> use B-M ... I can't find either "Boyer" or "Moore" in its source code.
>
> There's no particular reason to suppose offhand that a regex engine
> would be faster than the naive code for fixed patterns.

Well even a lame regexp implementation ought to be O(n+m). The factors will be
less than Boyer-Moore which can skip over substantial sections of the search
space without even looking at the characters. But there's no way it would be
O(n*m) for simple patterns unless the implementation was seriously deficient.

Of course your statement could still be true for particular usage patterns
like searching many different short strings with many different patterns where
the setup time of the regexp tables may dominate.

--
greg