[up for grabs]Two-way string searching

Andrea Fontana nospam at example.com
Mon Jun 17 01:04:12 PDT 2013


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


More information about the Digitalmars-d mailing list