[Bug libc/5514] memmem is O(n^2), but should be O(n)

["ebb9 at byu dot net" <sourceware-bugzilla at sourceware dot org>]

------- Additional Comments From ebb9 at byu dot net  2008-01-08 21:50 -------
Gnulib now has a reentrant linear-time constant-space solution for memmem, which
has the added benefit of sublinear speed for large enough needles:
http://git.sv.gnu.org/gitweb/?p=gnulib.git;a=blob;f=lib/memmem.c;h=622a034;hb=9d8d6cd

It also has a testsuite that exposes a couple of cases where the current glibc
takes orders of magnitude longer than the gnulib implementation to come up with
the same answer:
http://git.sv.gnu.org/gitweb/?p=gnulib.git;a=blob;f=tests/test-memmem.c

I'm still working on factoring the code to reuse the bulk of the algorithm in
strstr, strcasestr, strncasestr, and wcsstr (although sublinear speed there is
not an option, since the search for the NUL ending the haystack is an
unavoidable linear task), before posting the same code back here as a diff
against the glibc code base.


-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=5514

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.