http://volnitsky.com/project/str_search/
Reading this, two way algorithm doesn't seem the best one...
(author says it's used by GLIBC_memmem)
Have I missed the point?
On Sunday, 16 June 2013 at 22:17:04 UTC, Dmitry Olshansky wrote:
It have long bugged me that Phobos std.algorithm.find is slow.
Far slower then strstr (esp on *nix where it competes against
GLIBC[1]).
The current state of the art in searching substring
with O(1) space requirement is Two-Way algorithm:
http://www-igm.univ-mlv.fr/~lecroq/string/node26.html
which is linear in time.
I could imagine it would be interesting to implement a generic
version as well. Any takers? I'd gladly go for it myself but
unfortunately way too busy on other fronts (I planed to do it
for a couple of months already).
[1] See a relevant bug report and discussion e.g on glibc
http://sourceware.org/bugzilla/show_bug.cgi?id=5514
