Re: substring match like "strstr"

[Gerd Stolpmann <gerd@gerd-stolpmann.de>]

On Fri, 08 Dec 2000, eijiro_sumii@anet.ne.jp wrote:
>Hi all,
>
>Is there a substring matching function (like "strstr" in libc) in the
>standard OCaml library?  Of course there are many ways to implement it
>(by writing it from scratch, using the Str library, interfacing
>"strstr" in libc, etc.), but they are overkill for my purpose.  So I'm
>wondering whether such a function already exists, but I couldn't find
>it in the manual...

There isn't such a function.

You can write it yourself:

let find_substring s1 s2 =
  (* find s2 in s1, or raise Not_found *)
  if String.length s2 > String.length s1 then raise Not_found;
  let b = String.create (String.length s2) in
  let rec search k =
    if k > String.length s1 - String.length s2 then raise Not_found;
    String.blit ~src:s1 ~src_pos:k ~dst:b ~dst_pos:0 ~len:(String.length s2);
    if b = s2 then
      k
    else search (k+1)
  in
  search 0
;;

This version of find_substring avoids superflous heap allocations, and I think
it is tricky anough to be included into the stdlib. (However, if we had strstr
as primitive, even the allocation of b could be avoided.)

If speed is important, I recommend 

let find_substring s1 s2 =
  Str.search_forward (Str.regexp (Str.quote s2)) s1 0
;;

I hope these solutions aren't overkilling.

Gerd
-- 
----------------------------------------------------------------------------
Gerd Stolpmann      Telefon: +49 6151 997705 (privat)
Viktoriastr. 100             
64293 Darmstadt     EMail:   gerd@gerd-stolpmann.de
Germany                     
----------------------------------------------------------------------------