(**************************************************************************)
(*                                                                        *)
(*  Copyright (C) Jean-Christophe Filliatre                               *)
(*                                                                        *)
(*  This software is free software; you can redistribute it and/or        *)
(*  modify it under the terms of the GNU Library General Public           *)
(*  License version 2, with the special exception on linking              *)
(*  described in file LICENSE.                                            *)
(*                                                                        *)
(*  This software is distributed in the hope that it will be useful,      *)
(*  but WITHOUT ANY WARRANTY; without even the implied warranty of        *)
(*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                  *)
(*                                                                        *)
(**************************************************************************)

(*S Knuth-Morris-Pratt string search algorithm. *)

(*s [search p t] searches the first occurrence of pattern
    [p] in text [t]. It raises [Not_found] if [p] does not occur in [t].
    Strings are 0-based. Both arguments can be empty.
    If [p] is to be searched many times in different texts then a partial
    application [search p] is more efficient (the shift table is computed
    only once).

    Complexity: if [m] is the length of [p] and [n] the length of [t] then
    [search p t] runs in time $O(m+n)$ and uses $O(m)$ space.
*)

val search : string -> string -> int

(*s Functorial interface. Knuth-Morris-Pratt algorithm can be applied
    to patterns and texts of any type using the following functor. 
    Patterns and texts may be of different types, as soon as the type of 
    characters is common. [length s] must return the length of [s], and 
    [get s i] must return the [i]-th character of [s] (starting from 0).
    Equality on characters is supposed to be structural equality ([=]).
*)

module type STRING = sig
  type t 
  type char
  val length : t -> int
  val get : t -> int -> char
end

module Make(P : STRING)(T : STRING with type char = P.char) : sig

  val search : P.t -> T.t -> int

end

(*s Debugging: setting the following boolean reference to [true] will
    dump the shift table on error output. *)

val debug : bool ref