[up for grabs]Two-way string searching

Dmitry Olshansky dmitry.olsh at gmail.com
Sun Jun 16 15:16:50 PDT 2013


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


-- 
Dmitry Olshansky


More information about the Digitalmars-d mailing list