Re: Volnitsky substring search algo
| From: | Leonid Volnitsky | Date: | Thu, 03 Mar 2011 20:22:24 +0000 |
| Subject: | Re: Volnitsky substring search algo | ||
| References: | 1 2 | Groups: | php.internals |
| Request: | Send a blank email to internals+get-51564@lists.php.net to get a copy of this message | ||
Damien Tournoud <damz <at> damz.org> writes:
>
> On Sun, Feb 27, 2011 at 12:50 PM, Jordi Boggiano <j.boggiano <at> seld.be>
wrote:
> The algorithm seems flawed to me, at least in its reference implementation.
> There does not seem to be any guarantee that the returned position is really
> the *first* occurrence of the needle in the haystack.
This is a bug. This algorithm is still something very new.
> The implementation could be fixed (by adding an explicit string matching
> when building the hash table, and by storing *all* the occurrences of a
> given W in SS), but that will increase the overall cost (both computing and
> memory) of the algorithm.
Bug was fixed by reversing hash fill order (without increase of overall cost).
@ All
About the licence. I am not a layer, I need to figure out the licensing.
I intend to give PHP project a special license, I just need to clarify several
things.