(* $Id: netaux.mli,v 1.1 2002/01/14 23:47:15 stolpmann Exp $
 * ----------------------------------------------------------------------
 *
 *)

(* Auxiliary stuff *)


module KMP : sig
  (* An implementation of the Knuth-Morris-Pratt algorithm *)
  (* Credits go to Alain Frisch who suggested this algorithm *)

  type pattern

  val make_pattern : string -> pattern
    (* Prepares the passed pattern *)

  val find_pattern : pattern -> ?pos:int -> ?len:int -> string -> int
    (* Searches the position where the pattern or a prefix of the pattern
     * occurs in the substring from position [pos] to [pos+len-1]. 
     * Possible return values p:
     * - pos <= p <= pos+len-length(pattern):
     *   The pattern occurs at position p in the string, i.e.
     *   string.[p+k] = pattern.[k], for all 0 <= k < length(pattern).
     *   Furthermore, the returned position p is the first such position.
     * - pos+len-length(pattern) < p < pos+len
     *   The string ends with a prefix of the pattern, i.e.
     *   string.[p+k] = pattern[k], for all 0 <= k < pos+len-p.
     * - p = pos+len
     *   Neither does the pattern occur in the string, nor is the
     *   (non-empty) suffix of the string a prefix of the pattern.
     *
     * Defaults:
     * ~pos = 0
     * ~len = length(string)-pos = "until the end of the string"
     *)

end

(* ======================================================================
 * History:
 * 
 * $Log: netaux.mli,v $
 * Revision 1.1  2002/01/14 23:47:15  stolpmann
 * 	Initial revision
 *
 * 
 *)
