Info_MPSI/MP/kmp.ml

(*Vérifie que x appartient au mot t, il faut trouver l'entièreté de x*)
let recherche_iterative (t:string) (x:string) : bool = let i = ref 0 and j = ref 0 in
  while !i < String.length t && !j < String.length x do
    if t.[!i] = x.[!j] then 
      begin
      j := !j + 1;
      i := !i + 1
      end
    else
      begin
      j := 0; 
      i := !i + 1
    end
  done;
  !j = String.length x
;;

(*Trouver le bord strict d'un mot*)

let border_length (t:string) : int = 
  let i = ref 1 and j = ref 0 in
    while !i < String.length t && t.[!i] = t.[!j] do
      i := !i + 1;
      j := !j + 1
    done;
    !j
;;
let rec est_prefixe_recursif (t:char list) (x:char list) (copy_x: char list) :bool = match (t,x) with
| [],[] -> true
| [],_ -> false
| _,[] -> true
| t1::q1,t2::q2 -> if t1 = t2 then est_prefixe_recursif q1 q2 copy_x else est_prefixe_recursif q1 copy_x copy_x
;;

(*monpapimamamanmonpapamamaman*)
(*Recherche d'un mot en récursif, en utilisant est_prefixe_recursif*)

(*let rec recherche_recursif t x = match t with
| [] -> false
| t1::q1 -> if est_prefixe_recursif t1 x then true else recherche_recursif q1 x;;
*)

(*Renvoie le plus grand entier j tel que toute les lettres de entre vk et v(k+j-1) soient égales à wl ... w(l+j-1)*)
let compare_sub_strings (v:string) (k:int) (w:string) (l:int) (s:int) : int =
  let j = ref 0 in
    while !j < s && !j < String.length v -k + (!j) && !j < String.length w -l + (!j) && v.[k + !j] = w.[l + !j] do
      j := !j + 1
    done;
    !j
;;

compare_sub_strings "monpapimamamanmonpapamamaman" 0 "monpsdnv" 0 2;;

let test_egalite_sub_strings (v:string) (k:int) (w:string) (l:int) (s:int) : bool =
  s = compare_sub_strings v k w l s
;;

(*En testant les préfixes stricts du mot w un par un*)
(*Calcule la longueur du bord d'un mot w*)
(*Un bord est un préfixe et un suffixe*)
let border_length (w:string) : int =
  let n = String.length w in
    let k = ref (n-1) in
      while !k > 0 && not (test_egalite_sub_strings w 0 w (n - !k) !k) do
        k := !k - 1
      done;
      !k
;;

border_length "maacadamaa";;

let borders_naif w : int array = 
  let n = String.length w in
    let b = Array.make (n+1) (-1) in
      for i = 1 to n do
        b.(i) <- border_length (String.sub w 0 i)
      done;
      b
;;

borders_naif "ababaa";;

let kmp (t:string) (x:string) : bool =
  let deb = ref 0 and i = ref 0 and j = ref 0 in
    while !i < String.length t && !j < String.length x do
      if t.[!i] = x.[!j] then
        begin
        i := !i + 1;
        j := !j + 1
        end
      else
        begin
        j := 0;
        deb := !i + 1;
        i := !i + 1
        end
    done;
    !j = String.length x
;;