Adloun

Ordre lexicographique

Exercice · OCaml (option informatique), chapitre 6 — Caractères et chaînes de caractères

Énoncé

Sans utiliser < sur les chaînes, écrire avant s1 s2 qui teste si s1 précède s2 dans l'ordre du dictionnaire, en comparant caractère par caractère.

Corrigé

let avant s1 s2 =
  let n1 = String.length s1 and n2 = String.length s2 in
  let i = ref 0 in
  while !i < n1 && !i < n2 && s1.[!i] = s2.[!i] do
    i := !i + 1
  done;
  if !i = n1 then !i < n2          (* s1 épuisée : préfixe (ou égale) *)
  else if !i = n2 then false       (* s2 épuisée la première : s2 < s1 *)
  else s1.[!i] < s2.[!i]           (* premier caractère qui diffère *)

On avance tant que les caractères coïncident, puis on tranche : si s1 est épuisée, elle précède s2 sauf si elles sont égales ; sinon on compare le premier caractère distinct. C'est exactement ce que fait &lt; sur les chaînes.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.