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.
