(* TP 02 - Exercice 2 - Plus longue sous-séquence commune en OCaml *)

(* Détermine la longueur de la plus longue sous-séquence commune *)
let lplssc m1 m2 =
  (* A FAIRE *)
  let n1 = Array.length m1 in
  let n2 = Array.length m2 in
  let tab = Array.make_matrix (n1+1) (n2+1) 0 in
  for i = 1 to n1 do
    for j = 1 to n2 do
      if m1.(i-1) = m2.(j-1) then
        tab.(i).(j) <- 1 + tab.(i-1).(j-1)
      else
        tab.(i).(j) <- max tab.(i-1).(j) tab.(i).(j-1)
    done
  done; tab.(n1).(n2)
;;


(* Détermine la (une des) plus longue sous-séquence commune *)
let plssc m1 m2 =
  (* identique *)
  let n1 = Array.length m1 in
  let n2 = Array.length m2 in
  let tab = Array.make_matrix (n1+1) (n2+1) 0 in
  for i = 1 to n1 do
    for j = 1 to n2 do
      if m1.(i-1) = m2.(j-1) then
        tab.(i).(j) <- 1 + tab.(i-1).(j-1)
      else
        tab.(i).(j) <- max tab.(i-1).(j) tab.(i).(j-1)
    done
  done;
  (* on remonte dans le tableau pour construire la liste des valeurs communes *)
  let i = ref n1 in
  let j = ref n2 in
  let sc = ref [] in
  while tab.(!i).(!j) <> 0 do
    if m1.(!i-1) = m2.(!j-1) then begin
      sc := m1.(!i-1) :: !sc;
      decr i; decr j
    end else if tab.(!i-1).(!j) > tab.(!i).(!j-1) then 
      decr i
    else
      decr j
  done; !sc
;;

let m1 = [|1;7;4|];;
let m2 = [|3;1;4;3|];;
Printf.printf "lplssc %d\n" (lplssc m1 m2);;
List.iter print_int (plssc m1 m2);;
Printf.printf "\n";;

let m3 = [|2;4;1;2;4;4;2;1;2;7;2|];;
let m4 = [|1;2;4;6;4;5;2;4;1;7|];;
Printf.printf "\nlplssc %d\n" (lplssc m3 m4);;
List.iter print_int (plssc m3 m4);;
Printf.printf "\n";;