[up for grabs]Two-way string searching

Dmitry Olshansky dmitry.olsh at gmail.com
Mon Jun 17 09:58:58 PDT 2013


17-Jun-2013 12:04, Andrea Fontana пишет:
> 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?

No idea as I do not see Two way search represented here at all.
Otherwise all of the comments by Ivan apply.

>
> 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


-- 
Dmitry Olshansky


More information about the Digitalmars-d mailing list