[up for grabs]Two-way string searching

Ivan Kazmenko gassa at mail.ru
Mon Jun 17 05:40:36 PDT 2013


On Monday, 17 June 2013 at 08:04:14 UTC, Andrea Fontana wrote:
> 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?

That's a strange page, at a glance:

1. The algorithms were tested essentially on one real-life test 
case.
2. Author claims to use a structure similar to hash table, but 
does not include Rabin-Karp algorithm in comparison.
3. Reference implementation does not in fact allow online 
searching, but the algorithm is claimed to have the capacity.
4. Reference implementation has hardcoded constants for array 
sizes.
5. The comment about case-insensitive search seems inefficient at 
best: it suggests to hash every case combination (hello 
combinatorial explosion) instead of just converting everything to 
lowercase on the fly.
(and 6. Reference implementation didn't work for me, but it may 
be actually my fault...)

Given the points above, I won't make any decisions based on data 
from that page :) .

Ivan Kazmenko.


More information about the Digitalmars-d mailing list