(* Distance et chemin entre deux mots *)
(* Alain FRISCH             mars 1998 *)

(*
   distance
   on evite la construction de la matrice complète en ne stockant
   que la ligne précédente (dans v) et la ligne en cours de
   construction (dans w)
*)

let distance a b =
  let n = string_length a
  and m = string_length b
  in
  let v = ref (make_vect (n+1) 0)
  and w = ref [||]
  in
    for i=0 to n do !v.(i)<-i done;
    for j=1 to m do
      w:=make_vect (n+1) j;
      for i=1 to n do
        !w.(i)<- min (1+min !v.(i) !w.(i-1)) (if a.[i-1]=b.[j-1] then !v.(i-1) else 1+(!v.(i-1)))
      done;
      v:=!w;
    done;
    !v.(n);;

(*
   chemin
   on construit la même matrice, mais en stockant dans chaque case (i,j) un
   chemin minimal qui mène du i-ème prefixe de a au j-émé prefixe de b
*)

let chemin a b =
  let n = string_length a
  and m = string_length b
  in
  let v = ref (make_vect (n+1) (0,[]))
  and w = ref [||]
  and p (l,ch) = l+1,ch
  and plus_petit x y z =
    if (fst x<=fst y) & (fst x<=fst z) then 1,x
    else if (fst y<=fst x) & (fst y<=fst z) then 2,y
    else 3,z
  in
    !v.(0)<-0,[""];
    for i=1 to n do !v.(i)<-i,sub_string a 0 i::(snd !v.(i-1)) done;
    for j=1 to m do
      w:=make_vect (n+1) (j,[""]);
      !w.(0)<-j,(snd !v.(0))@[sub_string b 0 j];
      for i=1 to n do
        !w.(i)<-
        match (plus_petit (p !v.(i)) (p !w.(i-1)) (if a.[i-1]=b.[j-1] then !v.(i-1) else (p !v.(i-1))))
        with
          | 1,(l,ch) -> (l,ch@[sub_string b 0 j])
          | 2,(l,ch) -> (l,sub_string a 0 i ::ch)
          | _,(l,ch) ->
            let ch2=map (fun m->m^(char_for_read b.[j-1])) ch in
            if (a.[i-1]=b.[j-1]) then (l,ch2)
            else (l,sub_string a 0 i ::ch2)
      done;
      v:=!w;
    done;
    !v.(n);;



(* ESSAIS *)
chemin "abc" "acb";;
chemin "abc" "acbd";;
chemin "echarde" "charrue";;
chemin "knuth" "cheno";;
chemin "cheno" "chameau";;
chemin "caml is pretty" "pascal is beautiful";;
chemin "nelson monfort" "mets le son moins fort";;
chemin "zorglub" "glups";;
chemin "abcdef" "cdefg";;
chemin "tableau" "bateau";;
chemin "cuisine" "cousine";;
chemin "baguette" "claquette";;
chemin "abcdefgh" "hgfedcba";;
chemin "erreur" "horreur";;
chemin "roswell" "pradel";;
chemin "orthographe" "tomate";;
chemin "neige" "nagano";;
chemin "frankenstein" "fantastique";;

["abc"; "ac"; "acb"]
["abc"; "abd"; "acbd"]
["echarde"; "echarre"; "charre"; "charrue"]
["knuth"; "knuto"; "knuno"; "kneno"; "kheno"; "cheno"]
["cheno"; "chenu"; "cheau"; "chaeau"; "chameau"]
["caml is pretty"; "caml is pretti"; "caml is preati"; "caml is peati";
 "caml is beati"; "casl is beati"; "pasl is beati"; "pascl is beati";
 "pascal is beati"; "pascal is beauti"; "pascal is beautif";
 "pascal is beautifu"; "pascal is beautiful"]
["nelson monfort"; "melson monfort"; "metlson monfort"; "metslson monfort";
 "mets lson monfort"; "mets leson monfort"; "mets le son monfort";
 "mets le son moinfort"; "mets le son moinsfort"; "mets le son moins fort"]
["zorglub"; "zorglup"; "zoglup"; "zglup"; "glup"; "glups"]
["abcdef"; "acdef"; "cdef"; "cdefg"]
["tableau"; "tabeau"; "tateau"; "bateau"]
["cuisine"; "cusine"; "cousine"]
["baguette"; "baquette"; "caquette"; "claquette"]
["abcdefgh"; "abcdefgb"; "abcdefcb"; "abcdedcb"; "abcedcb"; "abfedcb";
 "agfedcb"; "hgfedcb"; "hgfedcba"]
["erreur"; "hrreur"; "horreur"]
["roswell"; "roswel"; "rosel"; "rodel"; "radel"; "pradel"]
["orthographe"; "orthogrape"; "orthograte"; "orthogate"; "orthomate";
 "ortomate"; "otomate"; "tomate"]
["neige"; "neiga"; "nega"; "naga"; "nagan"; "nagano"]
["frankenstein"; "frankensteiq"; "frankenstiq"; "frankestiq"; "frankastiq";
 "frantastiq"; "fantastiq"; "fantastiqu"; "fantastique"]