This is the mail archive of the glibc-bugs@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


------- 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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]