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

[ebb9 at byu dot net]

------- Additional Comments From ebb9 at byu dot net  2008-01-05 00:09 -------
I stand corrected - my claim that string searches are inherently quadratic in
space-time appears to be valid for arbitrary alphabets with no further
constraints.  But if [1] is to be believed, then the Two-Way algorithm provides
an algorithm that exploits an additional constraint of random access and a
sorted alphabet to provide an algorithm with the desirable properties of O(n)
time and O(1) space searching.  I'm not sure if strcasestr qualifies as using a
sorted alphabet, but memmem and strstr both do.  Therefore, I'll experiment with
coding the Two-Way algorithm in gnulib, and if it works, post the results here.

[1] http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260 


-- 


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.