Ordre lexicographique

Caractères et chaînes de caractères · niveau 2

É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 < sur les chaînes.

Énoncé

Corrigé

Exercices semblables