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

[bruno at clisp 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.