Caractères et chaînes de caractères

Cours complet · OCaml (option informatique), chapitre 6 · prépas MPSI et MP, option informatique

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>6.1 Introduction et motivation

Les données ne sont pas toujours des nombres : un nom, un mot de passe, une séquence d'ADN, le texte d'un fichier sont des suites de caractères. Ce chapitre présente les types char et string, ainsi que les fonctions de conversion entre types de base — comment passer d'un int à la chaîne "42" et réciproquement.

iRemarqueNiveau A.2

Comme les tableaux, les caractères, les chaînes et les conversions relèvent des éléments « utilisables après rappel » : leur documentation est fournie en épreuve. On les présente avec leur signature.

Une particularité guidera tout le chapitre : en OCaml, les chaînes sont immuables. On ne modifie pas une chaîne « en place » comme un tableau ; on en construit une nouvelle. Cela change la façon de programmer : on lit et analyse beaucoup, et l'on assemble par concaténation.

6.2 Les caractères

Le type char représente un caractère unique, écrit entre apostrophes : 'a', 'Z', '7', ' ' (l'espace).


# 'a';;
- : char = 'a'
# 'a' < 'b';;
- : bool = true

Définition 6.1Ordre et codes des caractères

Il existe une relation d'ordre total sur char : les comparaisons <, <=, etc. s'y appliquent. Cet ordre suit les codes numériques (codes ASCII) : les chiffres '0'…'9' se suivent, de même que 'a'…'z' et 'A'…'Z'. Deux conversions font le pont avec les entiers :

int_of_char c : char -> int — le code du caractère ;
char_of_int n : int -> char — le caractère de code n (pour 0 <= n <= 255).

Comme les chiffres et les lettres se suivent, on teste et on calcule sur les caractères par des comparaisons et des décalages de codes.

Exemple 6.2Tester et transformer un caractère


let est_chiffre c = c >= '0' && c <= '9'

let majuscule c =
  if c >= 'a' && c <= 'z'
  then char_of_int (int_of_char c - 32)   (* 'a' - 'A' = 32 *)
  else c

est_chiffre compare aux bornes '0' et '9'. majuscule décale le code de $32$ (l'écart entre minuscules et majuscules) ; les caractères non minuscules sont laissés tels quels.

6.3 Les chaînes de caractères

Le type string est une suite de caractères, écrite entre guillemets droits : "bonjour".

iRemarqueRappel (A.2)

String.length s : string -> int — le nombre de caractères ;
s.[i] : char — le caractère d'indice i (de 0 à String.length s - 1) ;
s1 ^ s2 : string -> string -> string — la concaténation.


# String.length "bonjour";;
- : int = 7
# "bon".[2];;
- : char = 'n'
# "bon" ^ "jour";;
- : string = "bonjour"

ImportantLes chaînes sont immuables

On lit un caractère par s.[i], mais on ne peut pas l'écrire : s.[i] <- c n'existe pas pour une string. Pour obtenir une chaîne « modifiée », on en construit une nouvelle (par concaténation). C'est la différence majeure avec le tableau du chapitre précédent : char array serait modifiable, string ne l'est pas.

L'ordre sur les chaînes est l'ordre du dictionnaire (lexicographique), induit par l'ordre sur les caractères : "abc" < "abd" et "abc" < "abcd" valent true.

6.4 Les conversions entre types de base

Convertir entre nombres, booléens et chaînes est constant en programmation (lire une entrée, afficher un résultat).

iRemarqueRappel des conversions (A.2)

string_of_int : int -> string et int_of_string : string -> int ;
string_of_float, float_of_string ;
float_of_int, int_of_float (déjà vues au chapitre 1) ;
int_of_char, char_of_int.


# string_of_int 42;;
- : string = "42"
# int_of_string "100" + 1;;
- : int = 101

Attention

int_of_string lève l'exception Failure si la chaîne ne représente pas un entier : int_of_string "abc" échoue. On n'applique ces conversions qu'à des chaînes dont on contrôle le format.

6.5 Lire et analyser une chaîne

Comme un tableau, une chaîne se parcourt par indices avec une boucle for, de 0 à String.length s - 1, en lisant s.[i].

Exemple 6.3Compter un caractère


let compte c s =
  let n = ref 0 in
  for i = 0 to String.length s - 1 do
    if s.[i] = c then n := !n + 1
  done;
  !n

compte 'o' "bonjour" vaut 2. Le schéma — une référence accumulatrice, un parcours par indices — est exactement celui des tableaux : une chaîne se lit comme un tableau de caractères en lecture seule.

6.6 Construire des chaînes

On assemble des chaînes avec ^, à partir de littéraux et de conversions.


let bilan a b =
  string_of_int a ^ " + " ^ string_of_int b ^ " = " ^ string_of_int (a + b)

Complexité : Le coût de la concaténation répétée

s1 ^ s2 crée une nouvelle chaîne en recopiant les deux opérandes : son coût est proportionnel à la longueur totale. Concaténer dans une boucle (r := !r ^ ... à chaque tour) recopie l'accumulateur grandissant à chaque étape, d'où un coût quadratique — le même piège que l @ [x] sur les listes. Pour de gros assemblages, on utiliserait un tampon (module Buffer), hors programme ; sur de petites chaînes, la concaténation reste commode.

<i class="fa-solid fa-dumbbell mr-2" style="color:#2E7559"></i>6.7 Exercices résolus

Niveau $⋆$ (application directe du cours)

Exercice 1 : Type et valeur

Donner le type et la valeur affichés.


'Z' ;;   String.length "ocaml" ;;   "abc".[0] ;;   "a" ^ "b" ^ "c" ;;   '0' < '9' ;;

Démonstration


- : char = 'Z'
- : int = 5
- : char = 'a'
- : string = "abc"
- : bool = true

"abc".[0] renvoie un char (le premier caractère), pas une chaîne d'un caractère. Et '0' < '9' car les chiffres se suivent dans l'ordre des caractères.

Exercice 2 : Caractère chiffre

Écrire est_chiffre c, puis valeur c qui, pour un caractère chiffre, renvoie l'entier correspondant ('7' $\mapsto$ 7).

Démonstration


let est_chiffre c = c >= '0' && c <= '9'

let valeur c = int_of_char c - int_of_char '0'

valeur exploite que les chiffres ont des codes consécutifs : int_of_char '7' - int_of_char '0' = 7. Précondition : c est un chiffre.

Exercice 3 : Compter un caractère

Écrire compte c s (nombre d'occurrences de c dans s) et l'appliquer à compte 's' "mississippi".

Démonstration


let compte c s =
  let n = ref 0 in
  for i = 0 to String.length s - 1 do
    if s.[i] = c then n := !n + 1
  done;
  !n

compte 's' "mississippi" vaut 4. On parcourt les indices valides 0 à String.length s - 1.

Niveau $⋆ ⋆$ (raisonnement intermédiaire)

Exercice 4 : Palindrome

Écrire est_palindrome s (la chaîne se lit pareil dans les deux sens).

Démonstration


let est_palindrome s =
  let n = String.length s in
  let ok = ref true in
  for i = 0 to n / 2 - 1 do
    if s.[i] <> s.[n - 1 - i] then ok := false
  done;
  !ok

On compare le caractère i à son symétrique n-1-i, pour i jusqu'au milieu. Aucune construction de chaîne : on lit seulement. est_palindrome "kayak" vaut true, est_palindrome "ocaml" vaut false.

Exercice 5 : Somme des chiffres d'une chaîne

Écrire somme_chiffres s, somme des chiffres d'une chaîne ne contenant que des chiffres (ex. "1234" $\mapsto$ 10).

Démonstration


let somme_chiffres s =
  let total = ref 0 in
  for i = 0 to String.length s - 1 do
    total := !total + (int_of_char s.[i] - int_of_char '0')
  done;
  !total

Chaque caractère est converti en sa valeur numérique par l'écart de codes, puis ajouté. La précondition (« que des chiffres ») garantit que l'écart est bien dans 0…9.

Exercice 6 : Ordre lexicographique

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.

Démonstration


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.

Exercice 7 : Conversions

Écrire incremente_texte s qui, d'une chaîne représentant un entier, renvoie la chaîne de l'entier suivant ("99" $\mapsto$ "100").

Démonstration


let incremente_texte s = string_of_int (int_of_string s + 1)

On lit l'entier (int_of_string), on ajoute 1, on réécrit la chaîne (string_of_int). Le calcul se fait sur l'int, pas sur les caractères. Attention : int_of_string échoue si s n'est pas un entier valide.

Niveau $⋆ ⋆ ⋆$ (approfondissement)

Exercice 8 : Compter les mots

Écrire compte_mots s, le nombre de mots (suites maximales de caractères non-espaces) de s.

Démonstration


let compte_mots s =
  let n = ref 0 and dans_mot = ref false in
  for i = 0 to String.length s - 1 do
    if s.[i] = ' ' then dans_mot := false
    else begin
      if not !dans_mot then n := !n + 1;   (* début d'un nouveau mot *)
      dans_mot := true
    end
  done;
  !n

On maintient un drapeau dans_mot : on compte un mot de plus chaque fois qu'on entre dans une zone de non-espaces (transition espace $\to$ lettre). compte_mots " le chat dort " vaut 3. C'est un petit automate à deux états.

Exercice 9 : Répéter une chaîne

Écrire repete s n qui renvoie s concaténée n fois (repete "ab" 3 $=$ "ababab"). Discuter le coût.

Démonstration


let repete s n =
  let r = ref "" in
  for _i = 1 to n do
    r := !r ^ s
  done;
  !r

On part de la chaîne vide "" et on concatène s à chaque tour. Coût : à l'étape k, l'accumulateur a déjà longueur k |s| et est recopié — le total est quadratique* en n. Pour de grandes valeurs, un tampon (Buffer, hors programme) ramènerait au linéaire ; ici la version simple suffit.

Exercice 10 : Recherche d'un motif

Écrire contient s m qui teste si la chaîne m (le motif) apparaît dans s, par recherche naïve.

Démonstration


let contient s m =
  let ns = String.length s and nm = String.length m in
  let trouve = ref false in
  for i = 0 to ns - nm do
    let ok = ref true in
    for j = 0 to nm - 1 do
      if s.[i + j] <> m.[j] then ok := false
    done;
    if !ok then trouve := true
  done;
  !trouve

Pour chaque position de départ i (de 0 à ns - nm), on vérifie que les nm caractères coïncident. Le coût est $Θ (n_{s} \cdot n_{m})$ dans le pire cas. Si m est plus longue que s, la borne ns - nm est négative et la boucle ne s'exécute pas : false, comme attendu.

Synthèse du chapitre (à retenir)

char : caractère entre apostrophes ('a') ; ordre total (codes ASCII) ; int_of_char / char_of_int pour calculer sur les codes.
string : String.length s, accès s.[i] (un char), concaténation ^, ordre lexicographique. Immuable : pas de s.[i] <- c — on construit une nouvelle chaîne.
Conversions : string_of_int/int_of_string, string_of_float/float_of_string, int_of_char/char_of_int. int_of_string lève Failure sur un format invalide.
Analyser : parcours for i = 0 to String.length s - 1 lisant s.[i] — comme un tableau en lecture seule (compter, palindrome, mots, motif).
Construire par ^ et string_of_* ; concaténation répétée en boucle $=$ coût quadratique (comme l @ [x]).

6.8 Exercices d'entraînement

Légende : $⋆$ application directe, $⋆ ⋆$ raisonnement intermédiaire, $⋆ ⋆ ⋆$ approfondissement ; $⧫$ signale un classique incontournable. La numérotation prolonge celle des dix exercices résolus.

Thème A — Caractères.

[11.] $⋆$ Donner la valeur de int_of_char '0', char_of_int (int_of_char 'a' + 1), 'b' <= 'a'.
[12.] $⋆$ Écrire est_minuscule c et est_lettre c.
[13.] $⋆ ⋆$ $⧫$ Écrire minuscule c (l'inverse de majuscule du cours).

Thème B — Analyse de chaînes.

[14.] $⋆$ Écrire compte_voyelles s (nombre de a, e, i, o, u, y).
[15.] $⋆ ⋆$ Écrire tout_en_majuscules s : bool (la chaîne ne contient-elle aucune minuscule ?), en s'arrêtant au premier défaut.
[16.] $⋆ ⋆ ⋆$ Écrire position c s : int option (indice de la première occurrence de c, ou None).

Thème C — Conversions et construction.

[17.] $⋆ ⋆$ Écrire somme_texte s qui, pour une chaîne du type "12", renvoie l'int $12$ — sans int_of_string, en accumulant chiffre par chiffre (r := !r * 10 + valeur s.[i]).
[18.] $⋆ ⋆$ $⧫$ Écrire enumere n qui renvoie la chaîne "1 2 3 ... n" (entiers séparés par des espaces).
[19.] $⋆ ⋆ ⋆$ Écrire en_majuscules s qui renvoie une copie de s tout en majuscules, en concaténant les caractères transformés ; commenter le coût et la limite de la concaténation répétée.

Thème D — Recherche et comparaison.

[20.] $⋆ ⋆$ Écrire commence_par s prefixe : bool (s commence-t-elle par prefixe ?).
[21.] $⋆ ⋆ ⋆$ Écrire compte_occurrences m s : le nombre d'apparitions (éventuellement chevauchantes) du motif m dans s.
[22.] $⋆ ⋆ ⋆$ $⧫$ Écrire anagrammes s1 s2 : bool : s1 et s2 sont-elles formées des mêmes lettres (mêmes occurrences) ? (Indication : un tableau de comptage indexé par int_of_char.)

Continuer sur Adloun : animation, QCM, fiches, exercices

Caractères et chaînes de caractères

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>6.1 Introduction et motivation

6.2 Les caractères

6.3 Les chaînes de caractères

6.4 Les conversions entre types de base

6.5 Lire et analyser une chaîne

6.6 Construire des chaînes

Complexité : Le coût de la concaténation répétée

<i class="fa-solid fa-dumbbell mr-2" style="color:#2E7559"></i>6.7 Exercices résolus

Niveau ⋆ (application directe du cours)

Niveau ⋆⋆ (raisonnement intermédiaire)

Niveau ⋆⋆⋆ (approfondissement)

6.8 Exercices d'entraînement

Thème A — Caractères.

Thème B — Analyse de chaînes.

Thème C — Conversions et construction.

Thème D — Recherche et comparaison.

Niveau $⋆$ (application directe du cours)

Niveau $⋆ ⋆$ (raisonnement intermédiaire)

Niveau $⋆ ⋆ ⋆$ (approfondissement)