Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:51540
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain seld.be designates 74.125.82.170 as permitted sender)
Message-ID: <4D6A3A9C.50308@seld.be>
Date: Sun, 27 Feb 2011 12:50:52 +0100
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 6.1; en-US; rv:1.9.2.12) Gecko/20101027 Lightning/1.0b2 Thunderbird/3.1.6
MIME-Version: 1.0
To: "internals@lists.php.net" <internals@lists.php.net>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Subject: Volnitsky substring search algo
From: j.boggiano@seld.be (Jordi Boggiano)

Heya,

I just wanted to attract attention to this new substring search
algorithm that seems faster better stronger.. According to the author of
course. I don't quite have the required knowledge to evaluate this
properly, but thought it was worth investigating if someone wants to.

http://volnitsky.com/project/str_search/

Note that I contacted the author and although he intends to release it
as GPL, he said he would probably give out a special license for PHP if
needed, since the GPL is afaik not compatible with the PHP license.

He also said that his algo was more useful for big haystacks than small
ones due to the startup overhead, but it seems that his code is anyway
falling back to std::search for smallish haystacks.

Cheers

-- 
Jordi Boggiano
@seldaek :: http://seld.be/