(* Sous-mot et facteur d'un mot *)

(* Utilitaires *)
let list_of_string s = 
  let rec aux accu = function
  | 0 -> accu
  | i -> aux (s.[i-1]::accu) (i-1)
  in aux [] (string_length s)
;;

let rec string_of_list = function
  | [] -> ""
  | t::q -> (char_for_read t)^(string_of_list q)
;;

(* Sous-mot *)
let sous_mot mot ssmot = 
  let rec cherche = fun
    | _ [] -> true
    | [] _ -> false
    | (t::q) (tss::qss) when t = tss -> cherche q qss
    | (_::q) ssm -> cherche q ssm
  in cherche (list_of_string mot) (list_of_string ssmot)
;;

(* Facteur *)
let facteur mot fact = 
  let fac_l = list_of_string fact
  in let rec cherche = function
    | _,[] -> true
    | [],_ -> false
    | t::q,tss::qss -> (t=tss && cherche_intern (q,qss)) || cherche (q,fac_l)
     and cherche_intern = function
       | _,[] -> true
       | [],_ -> false
       | t::q,tss::qss -> t=tss && cherche_intern (q,qss)
  in cherche (list_of_string mot,fac_l)
;;

(* Knuth-Morris-Pratt *)
let facteur_KMP mot fac = 
  let lg_mot = string_length mot and lg_fac = string_length fac
  in let overlap_val = make_vect (lg_fac+1) (-1)
  in let rec compute_overlap i = 
      overlap_val.(i) <- (overlap (i-1)) + 1;
       while (overlap_val.(i) > 0 && fac.[i-1] <> fac.[(overlap i)-1]) do
         overlap_val.(i) <- (overlap(overlap i)-1) + 1
       done
     and overlap i = 
      if (i < 0 || i > lg_fac)
      then failwith ("Erreur : index trop grand ou trop petit "^(string_of_int i))
      else 
        begin
          if (i<>0 && overlap_val.(i) = -1) then compute_overlap i;
          overlap_val.(i);
        end
  in let rec cherche (i,j) = match (i = lg_mot, j = lg_fac) with
    | _,true -> true
(*  | _,true -> (print_string "Trouvé !\n"; cherche (i+(max 1 (j-(overlap j))), overlap j))*)
    | true,_ -> false
    | _ ->
        if mot.[i+j] = fac.[j]
        then cherche (i, j+1)
        else cherche (i+(max 1 (j-(overlap j))), overlap j)
  in
    compute_overlap 4; overlap_val.(0) <- 0;
    cherche (0, 0)
;;

facteur_KMP "banananobano" "nano";;