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 TAA13925 for caml-red; Thu, 14 Dec 2000 19:00:36 +0100 (MET)
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id NAA11520 for <caml-list@pauillac.inria.fr>; Tue, 12 Dec 2000 13:28:44 +0100 (MET)
Received: from ext.lri.fr (ext.lri.fr [129.175.15.4])
	by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id eBCCShX01912
	for <caml-list@inria.fr>; Tue, 12 Dec 2000 13:28:43 +0100 (MET)
Received: from pc803.lri.fr (IDENT:root@pc803 [129.175.8.114])
          by ext.lri.fr (8.11.1/jtpda-5.3.2) with ESMTP id eBCCSbQ14814
          ; Tue, 12 Dec 2000 13:28:37 +0100 (MET)
Received: by pc803.lri.fr
	(8.9.3/feuille) id NAA05020
	; Tue, 12 Dec 2000 13:28:32 +0100
X-Authentication-Warning: localhost.localdomain: filliatr set sender to filliatr@pc803 using -f
From: Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Message-ID: <14902.6640.301542.507040@pc803>
Date: Tue, 12 Dec 2000 13:28:32 +0100 (MET)
To: Chris Hecker <checker@d6.com>
Cc: gerd@gerd-stolpmann.de, eijiro_sumii@anet.ne.jp, caml-list@inria.fr,
        sumii@venus.is.s.u-tokyo.ac.jp
Subject: Re: substring match like "strstr"
In-Reply-To: <4.3.2.7.2.20001211202018.00b3f510@shell16.ba.best.com>
References: <4.3.2.7.2.20001211103237.00c12100@shell16.ba.best.com>
	<00120814135508.00625@ice>
	<0012112341150J.00625@ice>
	<4.3.2.7.2.20001211202018.00b3f510@shell16.ba.best.com>
X-Mailer: VM 6.49 under Emacs 20.4.1
Reply-To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre)
Sender: weis@pauillac.inria.fr


Hello,

I   missed  the   beginning  of   the  discussion,   but  implementing
Knuth-Morris-Pratt is quite easy. The  code is given below (26 lines),
following Sedgewick's book "Algorithms".  Notice that the function kmp
can be partially applied to  a pattern, therefore computing the offset
table only once. The complexity is N+M where N is the size of the text
and M the size of the pattern.

(The following program was proved  correct in the Coq Proof Assistant;
without the Not_found exception, however)

Hope this helps,
-- 
Jean-Christophe FILLIATRE
  mailto:Jean-Christophe.Filliatre@lri.fr
  http://www.lri.fr/~filliatr

======================================================================
let initnext p =
  let m = String.length p in
  let next = Array.create m 0 in
  let i = ref 1 and j = ref 0 in
  while !i < m-1 do
    if p.[!i] = p.[!j] then begin
      incr i; incr j; next.(!i) <- !j
    end else
      if !j = 0 then begin incr i; next.(!i) <- 0 end else j := next.(!j)
  done;
  next

let kmp p =
  let next = initnext p in
  fun a ->
    let n = String.length a
    and m = String.length p
    and i = ref 0
    and j = ref 0 in
    while !j < m & !i < n do
      if a.[!i] = p.[!j] then begin
	incr i; incr j
      end else
	if !j = 0 then incr i else j := next.(!j)
    done;
    if !j >= m then !i-m else raise Not_found
======================================================================