Re: substring match like "strstr"

[eijiro_sumii@anet.ne.jp]

> Okay, I'm curious, so I'll port the code to caml and include it
> below as well (as practice for myself).  Can you try it in your test
> harness?

I tried the optimized version of the imperative strstr, along with an
optimized version of the functional strstr (attached at the end).  The
results (on the SPARC machine) were:

	strstr_imp2	90.57
	strstr_fun2	89.64
	C strstr	53.76

So the imperative version and the functional version were comparable,
though both were slower than the C version.  My guess is that they
actually compile into rather similar code, because all recursive calls
are in tail positions.

Anyway, for my application, the libc version seems the most reasonable
choice, as far as I use a strstr-like function at all...

// Eijiro Sumii (http://www.yl.is.s.u-tokyo.ac.jp/~sumii/)
// 
// Ph.D. Student at Department of IS, University of Tokyo
// Visiting Scholar at Department of CIS, University of Pennsylvania

let strstr_fun2 pat str =
  let patlim = String.length pat - 1 in
  let strlim = String.length str - 1 in
  let rec sub patpos strpos =
    (* compare pat[0..patpos] and str[(strpos-patpos)..strpos] *)
    if patpos < 0 then true else
    if pat.[patpos] <> str.[strpos] then false else
    sub (patpos - 1) (strpos - 1) in
  let rec search strpos =
    (* compare pat[0..patlim] and str[(strpos-patlim)..strpos] *)
    if strpos > strlim then raise Not_found else
    if sub patlim strpos then strpos - patlim else
    search (strpos + 1) in
  search patlim
;;