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

[Brian H. <bri...@ql...>]

On Thu, 22 May 2003, Remi Vanicat wrote:

> well, in the original code, one have :
> 
> let kmp p =
>   let next = init_next p
>   and m = String.length p in
>   function s ->
> 
> So Partial application of the first argument already compute the next
> table. and so you can call the computed function on several different
> string. 

Check.  I'd missed that.  On the other hand, you compute the length of p 
twice- once in kmp and once in init_next.  Which is what I was trying to 
eliminate.  Maybe I was being stupid- how expensive is a String.length?  I 
was assuming it was O(n), linear with the length of the string.

Could we still preserve this, and only do a single string match, with code 
something like:

let find p =
    let m = String.length p in
    let next = String.KMP.compile' p m in
    fun s -> String.KMP.match' next m s

Where compile' and match' are versions of compile and match that take 
pre-computed string lengths-

let compile p = compile' p (String.length p)
and match pat s = match' pat (Array.length pat) s

?

Brian