Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:51564 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 27077 invoked from network); 3 Mar 2011 20:25:15 -0000 Received: from unknown (HELO lists.php.net) (127.0.0.1) by localhost with SMTP; 3 Mar 2011 20:25:15 -0000 Authentication-Results: pb1.pair.com smtp.mail=php-php-dev@m.gmane.org; spf=pass; sender-id=pass Authentication-Results: pb1.pair.com header.from=leonid@volnitsky.com; sender-id=unknown Received-SPF: pass (pb1.pair.com: domain m.gmane.org designates 80.91.229.12 as permitted sender) X-PHP-List-Original-Sender: php-php-dev@m.gmane.org X-Host-Fingerprint: 80.91.229.12 lo.gmane.org Linux 2.6 Received: from [80.91.229.12] ([80.91.229.12:44049] helo=lo.gmane.org) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ESMTP id 45/82-14579-629FF6D4 for ; Thu, 03 Mar 2011 15:25:13 -0500 Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1PvF57-0002b4-Af for internals@lists.php.net; Thu, 03 Mar 2011 21:25:05 +0100 Received: from 109.86.60.196 ([109.86.60.196]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Thu, 03 Mar 2011 21:25:05 +0100 Received: from leonid by 109.86.60.196 with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Thu, 03 Mar 2011 21:25:05 +0100 X-Injected-Via-Gmane: http://gmane.org/ To: internals@lists.php.net Date: Thu, 3 Mar 2011 20:22:24 +0000 (UTC) Lines: 28 Message-ID: References: <4D6A3A9C.50308@seld.be> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Gmane-NNTP-Posting-Host: sea.gmane.org User-Agent: Loom/3.14 (http://gmane.org/) X-Loom-IP: 109.86.60.196 (Mozilla/5.0 (X11; U; Linux x86_64; en-US) AppleWebKit/534.15 (KHTML, like Gecko) Chrome/10.0.612.1 Safari/534.15) Subject: Re: [PHP-DEV] Volnitsky substring search algo From: leonid@volnitsky.com (Leonid Volnitsky) Damien Tournoud damz.org> writes: > > On Sun, Feb 27, 2011 at 12:50 PM, Jordi Boggiano 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.