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=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 49041BC6B for ; Fri, 27 Jul 2007 02:20:02 +0200 (CEST) Received: from smtp3-g19.free.fr (smtp3-g19.free.fr [212.27.42.29]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l6R0K1Ep017656 for ; Fri, 27 Jul 2007 02:20:01 +0200 Received: from smtp3-g19.free.fr (localhost.localdomain [127.0.0.1]) by smtp3-g19.free.fr (Postfix) with ESMTP id 9DC6038D9 for ; Fri, 27 Jul 2007 02:20:01 +0200 (CEST) Received: from [192.168.0.5] (rke75-3-82-229-183-156.fbx.proxad.net [82.229.183.156]) by smtp3-g19.free.fr (Postfix) with ESMTP id 7D5743887 for ; Fri, 27 Jul 2007 02:20:01 +0200 (CEST) Message-ID: <46A93A06.7060704@frisch.fr> Date: Fri, 27 Jul 2007 02:19:18 +0200 From: Alain Frisch User-Agent: Thunderbird 2.0.0.5 (Windows/20070716) MIME-Version: 1.0 To: caml-list@inria.fr Subject: Re: [Caml-list] Knuth-Morris-Pratt References: <18088.39868.902524.369354@serveur9-10.lri.fr> <4a051d930707260727q31794e28pb388151a163209b7@mail.gmail.com> In-Reply-To: <4a051d930707260727q31794e28pb388151a163209b7@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 46A93A31.002 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; frisch:01 frisch:01 icfp:01 wrote:01 caml-list:01 alain:01 alain:01 hmm:04 bottleneck:08 christopher:08 useful:09 real:10 wrong:10 suspected:10 maybe:10 Christopher L Conway wrote: > 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... Boyer-Moore is more useful with a large alphabet. With only 4 characters, I don't think it would have helped you a lot for the contest (I might be wrong). -- Alain