Re: strpos() && KMP

Pavel Ajtkulov <ajtkulov@acm.org> writes:
> Patch intends for artificial language (for example DNA, or
> language with small alphabet, or regular language) only.
> In natural language, KMP(and other search algo) haven't notable
> advantages (+-5% time execution).

I wonder why you didn't propose Boyer-Moore instead, as that would have
some advantage for natural language text as well.

The difficulty with B-M is the need for a table indexed by character
code, which at first glance looks impractical for wchars.  But it seems
to me that we could use "wchar % 256" as the table index, meaning that
wchars with the same trailing byte share the same table entry.  That
would lose some efficiency compared to an exact implementation, but the
limited table size would outweigh that except in the most pathological
cases.

            regards, tom lane