Re: memmem speedup

[James Youngman]

On Jan 8, 2008 1:32 PM, Eric Blake <address@hidden> wrote:

> (I may later factor out the two_way static functions into a parameterized
> header, in order to share code with strstr, strcasestr, ...; however, note
> that strstr can never achieve sublinear performance, because it costs O(n)
> to find the NUL byte that terminates the haystack, and it is not safe to
> read beyond the NUL).

It may be generally useful for applications to have some way of
indicating that they are searching for a constant needle in a large
number of haystacks.  In such cases, the preparation only needs to be
done once at all.   In the specific case of findutils, locate will
typically search for a single needle in one or two million haystacks.
 Of course, locate also always knows the length of both the needle and
the haystack, too.

James.