Dug up this historic example from glibc of why optimizing compilers are a necessary mitigation against hideous code: https://sourceware.org/git/?p=glibc.git;a=blob;f=string/strstr.c;hb=0ecb606cb6cf65de1d9fc8a919bceb4be476c602 …
No, it's much slower. BM isn't constant-space, but there are at least two known, very good constant-space and linear-time algorithms.
-
-
Doesn't BM become linear time with Galil's addition? What are the two known alternative algorithms?
-
The problem is failure to be constant-space. strstr needs ability to run in constant-space because it does not admit errors.
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.