type chaine = char list

let textes = ["aab"; "abab"; "abbbaa"; "babaa"; "aaaba"; "abbabba"]

(* Question 2 *)
let chaine_of_string (s:string) :chaine =
  let res = ref [] in
  for i = 0 to (String.length s) -1 do
    res := s.[i]::(!res)
  done;
  List.rev !res

let _ = chaine_of_string "abbab"

(* Question 4 *)
let rec purge (s:chaine) :chaine =
  match s with
  |[]  |[_] -> s
  |'*'::'*'::q -> purge ('*'::q)
  |a::q -> a::(purge q)

let mp = purge (chaine_of_string "***ab**?a")

(* Question 5 *)
let rec respecte_naif (motif:chaine) (texte:chaine) :bool =
  match motif, texte with
  |[], [] -> true
  |['*'], [] -> true
  |_, [] -> false
  |[], _ -> false
  |a::b, c::d when a = c || a = '?' -> respecte_naif b d
  |'*'::b, _::d -> (respecte_naif b texte) || (respecte_naif motif d)
  |_ -> false (*cas d'une lettre dans le motif qui ne correspond pas au texte*)

let _ = List.map (respecte_naif mp) (List.map chaine_of_string textes)


(* Question 7 *)
let respecte_dynamique (motif:string) (texte:string) :bool =
  let n = String.length motif in
  let m = String.length texte in
  let res = Array.make_matrix (n+1) (m+1) false in
  res.(0).(0) <- true;
  res.(1).(0) <- motif.[0] = '*';
  for i = 1 to n do
    for j = 1 to m do
      match motif.[i-1] with
      |'?' -> res.(i).(j) <- res.(i-1).(j-1)
      |'*' -> res.(i).(j) <- res.(i-1).(j) || res.(i).(j-1)
      |_ -> res.(i).(j) <- res.(i-1).(j-1) && motif.[i-1] = texte.[j-1]
    done;
  done; 
  res.(n).(m)

let _ = List.map (respecte_dynamique "*ab*?a") textes
