Re: [Ocaml-lib-devel] ExtString module updated

[Michal M. <mal...@pl...>]

On Thu, May 22, 2003 at 10:51:25AM -0500, Brian Hurt wrote:
> On Thu, 22 May 2003, Michal Moskal wrote:
> 
> > On Thu, May 22, 2003 at 06:51:04PM +0900, Nicolas Cannasse wrote:
> > > > > val find : string -> string -> int  (* find a substring *)
> > > >
> > > > Using KMP or some other technique? (i.e. if it takes O(m * n), where m and
> > > > n are lengths of strings respectively? or O(log m * n + m))
> > > 
> > > Right now only a naive O(m*n) technique. Please check the CVS, and submit me
> > > some code if you have a better implementation.
> > 
> > You can have a look at http://caml.inria.fr/Examples/oc/basics/kmp.ml
> > 
> > I tried rewrite of while loop to tail recursion, but it looks ugly.
> > 
> > 
> 
> Sanity check this code, if you will:
> 
> let kmp p =
>     let m = String.length p in
>     let init_next p = 
>         let next = Array.create m 0 in
>         let rec loop i j =
>             if i >= (m - 1) then next
                      ^^^^^^^

I'm not quite sure how good is ocamlc wrt moving constants out of loop,
but probably moving this substraction out of the loop would be The Right
Thing.

> I don't think it's that ugly.  

Matter of taste I believe.

> And it gets rid of all the references- 
> which probably means a speed up (haven't tested it yet though).  

Maybe refs are optimized away by the compiler? But I don't know.

> Although 
> one thing we might want to consider: actually exporting the kmp_init 
> function and kmp function seperately.  This way if I wanted to find the 
> same substring in a lot of different strings, I don't have to constantly 
> recreate the next table.  Maybe something like:
[snip]

I think better as submodule:

extString.mli (or whatever):

module KMP = 
  sig
    type pattern
    val compile : string -> pattern
    val match : pattern -> string -> int
  end

val find : string -> string -> int

-- 
: Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::::: Wroclaw University, CS Dept : {E-,w}-- {b++,e}>+++ h