From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id TAA05371 for caml-red; Thu, 14 Dec 2000 19:22:26 +0100 (MET)
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id LAA28514 for <caml-list@pauillac.inria.fr>; Wed, 13 Dec 2000 11:53:20 +0100 (MET)
Received: from suburbia.net (suburbia.net [203.4.184.1])
	by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id eBDArGH05537
	for <caml-list@inria.fr>; Wed, 13 Dec 2000 11:53:18 +0100 (MET)
Received: by suburbia.net (Postfix, from userid 110)
	id D48FB6C53B; Wed, 13 Dec 2000 21:53:09 +1100 (EST)
To: eijiro_sumii@anet.ne.jp
Cc: caml-list@inria.fr, Jean-Christophe.Filliatre@lri.fr, jmp@arsdigita.com,
        sumii@venus.is.s.u-tokyo.ac.jp
Subject: Re: substring match like "strstr"
References: <0012112341150J.00625@ice> <4.3.2.7.2.20001211202018.00b3f510@shell16.ba.best.com> <14902.6640.301542.507040@pc803> <20001213190207A.sumii@yl.is.s.u-tokyo.ac.jp>
Cc: proff@iq.org
From: Julian Assange <proff@iq.org>
Date: 13 Dec 2000 21:53:09 +1100
In-Reply-To: eijiro_sumii@anet.ne.jp's message of "Wed, 13 Dec 2000 19:02:07 +0900"
Message-ID: <wxzoi0h9t6.fsf@suburbia.net>
User-Agent: Gnus/5.0802 (Gnus v5.8.2) XEmacs/21.1 (Big Bend)
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Sender: weis@pauillac.inria.fr

eijiro_sumii@anet.ne.jp writes:

> Hi everyone,
> 
> Thank you very much for a lot of kind advice!
> 
> Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr> wrote:
> > I   missed  the   beginning  of   the  discussion,   but  implementing
> > Knuth-Morris-Pratt is quite easy. The  code is given below (26 lines),
> 
> Actually, I found the (almost) same code on the web and tried it.  The
> results (again, execution time in seconds) were:
> 
> 		SPARC	Pentium
> 	strstr	52.68	57.050
> 	kmp	111.52	143.490

All of these more sophisticated methods are only going to be a win
when you are searching for larger strings. strstr is brutally simple,
has little setup/cleanup time, and hence is hard to beat for short
strings. Additionally gcc, will replace various s* calls with in-line
assembly versions. I'm not sure if this includes strstr (it is a
little more complicated than most).

Cheers,
Julian.