From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.0 required=5.0 tests=AWL,SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id 1F996BC6B for ; Thu, 26 Jul 2007 16:27:59 +0200 (CEST) Received: from wr-out-0506.google.com (wr-out-0506.google.com [64.233.184.234]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l6QERwxu022123 for ; Thu, 26 Jul 2007 16:27:58 +0200 Received: by wr-out-0506.google.com with SMTP id l58so332839wrl for ; Thu, 26 Jul 2007 07:27:58 -0700 (PDT) DKIM-Signature: a=rsa-sha1; c=relaxed/relaxed; d=gmail.com; s=beta; h=domainkey-signature:received:received:message-id:date:from:sender:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references:x-google-sender-auth; b=juVpLgvQ7Ll5tOTNM5oJje7Ln5Aa4zoCvGag7K3psmgdjLZUpA8Vo13kdHQhkYBO2st429+ADT/pwx+5iquZx/CiZ1OJzsBcst4y5xOIZJlJufL+21MJEppkJF9cCgdDHZboTZSYQg5+aa1OtJ00R6CpnpsWwvP0pKz9xrbVnOs= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:sender:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references:x-google-sender-auth; b=ILzedhm75DqQdbxwDne6RnQdP7RtxNIhdkEwe9vhmAxzn47eM0Xiw93gSVznBqrbPQBBkHJMfv/TKZ2VpPvWtfBtpeJFWp5ary+Gr2O7W0AQ9BD8x2b4N8eTTYIy0VBDVeHVYJemNerKVAGXPwCaIE5gBVoXFRGQLp6DXSE0QPw= Received: by 10.78.132.2 with SMTP id f2mr452716hud.1185460076912; Thu, 26 Jul 2007 07:27:56 -0700 (PDT) Received: by 10.78.156.10 with HTTP; Thu, 26 Jul 2007 07:27:56 -0700 (PDT) Message-ID: <4a051d930707260727q31794e28pb388151a163209b7@mail.gmail.com> Date: Thu, 26 Jul 2007 10:27:56 -0400 From: "Christopher L Conway" Sender: christopherleeconway@gmail.com To: "Jean-Christophe Filliatre" Subject: Re: [Caml-list] Knuth-Morris-Pratt Cc: caml-list@inria.fr In-Reply-To: <18088.39868.902524.369354@serveur9-10.lri.fr> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <18088.39868.902524.369354@serveur9-10.lri.fr> X-Google-Sender-Auth: 1317d3a9c4288024 X-Miltered: at discorde with ID 46A8AF6E.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; icfp:01 filliatre:01 filliatre:01 lri:01 icfp:01 ocaml:01 bazar:01 lri:01 filliatr:01 beginner's:01 ocaml:01 bug:01 beginners:01 wrote:01 wrote:01 Hmm. My KMP implementation turned out to be a real bottleneck in my ICFP code; I suspected I should have chosen Boyer-Moore (not knowing anything about the constant factors of each, just stabbing in the dark)... Maybe it was the average-case O(log n) "get" in my "rope" implementation... Chris On 7/26/07, Jean-Christophe Filliatre wrote: > > As a byproduct of the last ICFP programming contest, I'm releasing an > implementation of Knuth-Morris-Pratt string searching algorithm that I > wrote years ago. You can find it here, in my ocaml bazar: > > http://www.lri.fr/~filliatr/software.en.html > > Just in case it may be useful, as it finally happened to be for myself. > > -- > Jean-Christophe, a Caml Rider > > > _______________________________________________ > Caml-list mailing list. Subscription management: > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > >