This is the mail archive of the
glibc-bugs@sourceware.org
mailing list for the glibc project.
[Bug libc/5514] memmem is O(n^2), but should be O(n)
- From: "ebb9 at byu dot net" <sourceware-bugzilla at sourceware dot org>
- To: glibc-bugs at sources dot redhat dot com
- Date: 5 Jan 2008 00:09:42 -0000
- Subject: [Bug libc/5514] memmem is O(n^2), but should be O(n)
- References: <20071220133012.5514.ebb9@byu.net>
- Reply-to: sourceware-bugzilla at sourceware dot org
------- 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.