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: "bruno at clisp dot org" <sourceware-bugzilla at sourceware dot org>
- To: glibc-bugs at sources dot redhat dot com
- Date: 26 Dec 2007 16:18:21 -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 bruno at clisp dot org 2007-12-26 16:18 -------
Thanks for the explanations. I tried to modify the KMP algorithm to use
only bounded additional space, as permitted by alloca. See attached patches.
But the result is unfortunately only O(n*(m-tm)) instead of O(n*m), where tm
is the number of 'int's that can be stored on the stack, typically something
like tm = 1024. For the really hard cases, where m can easily be 1000000 or
similar, it hardly helps. Therefore I give up on this.
--
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.