Masar
Masar
Bac Tunisie
Informatique/SD-B
Entraîner la reconnaissance
SD-BStructures de données et modularité

Traitement de chaînes de caractères — palindrome, sous-chaîne, occurrences

Idée directrice

L'énoncé donne une chaîne de caractères et demande d'en extraire des informations (longueur, caractère à un indice, sous-chaîne) ou de la transformer (inverser, vérifier palindrome, compter les occurrences d'un caractère). La maîtrise des fonctions primitives Longueur, Sous_chaine, Concat et de la conversion Ord/Chr est essentielle.

Signature de reconnaissance — l'énoncé se trahit ainsi

« Écrire une fonction qui vérifie si une chaîne est un palindrome » ; « Écrire une fonction qui inverse une chaîne de caractères » ; « Écrire une fonction qui compte le nombre d'occurrences d'un caractère dans une chaîne » ; « Écrire une fonction qui recherche une sous-chaîne dans une chaîne »

Sujet principal

Exercice — dans l'esprit des sujets du bac

3 questionsCorrigé masqué

On note Longueur(S) la longueur d'une chaîne S, S[i] le i-ème caractère, Sous_chaine(S, i, n) la sous-chaîne de S commençant à i et de longueur n, et Concat(S1, S2) la concaténation.

  1. Écrire une fonction Inverser(S) qui retourne la chaîne S lue à l'envers.
    1. Appliquer à S = "INFORMATIQUE". Quel est le résultat ?
    2. En déduire une fonction EstPalindrome(S) qui retourne VRAI si S est un palindrome.
  2. Écrire une fonction NbOccChar(S, c) qui retourne le nombre d'occurrences du caractère c dans la chaîne S. Compter le nombre de 'I' dans "INFORMATIQUE".
  3. Écrire une fonction ContientSousChaine(S, P) qui retourne l'indice de la première occurrence de la chaîne P dans S, ou 0 si P n'est pas dans S. Chercher "MAT" dans "INFORMATIQUE".
Voir la correction commentéeAprès avoir posé votre démarche

1. Inverser une chaîne. Construction par parcours décroissant et concaténation.

TDOL : i entier (compteur) ; inv chaîne (résultat). Type/Nature : S chaîne en entrée.

DEF FN Inverser(S : chaîne) : chaîne
Variables i : entier ; inv : chaîne
Début
  inv ← ""
  Pour i de Longueur(S) à 1 (pas -1) faire
    inv ← Concat(inv, S[i])
  FinPour
  Retourner inv
Fin

Application : Inverser("INFORMATIQUE") = "EUQITAMROFNI". On retourne la chaîne inversée.

1.(b) Palindrome.

DEF FN EstPalindrome(S : chaîne) : booléen
Début
  Retourner (S = Inverser(S))
Fin

Variante sans construire l'inverse : pour i de 1 à Longueur(S) div 2, vérifier S[i] = S[Longueur(S)-i+1].

2. Occurrences d'un caractère.

DEF FN NbOccChar(S : chaîne ; c : caractère) : entier
Variables i, n : entier
Début
  n ← 0
  Pour i de 1 à Longueur(S) faire
    Si S[i] = c alors n ← n + 1 FinSi
  FinPour
  Retourner n
Fin

Pour S = "INFORMATIQUE", c = 'I' : On retourne 2. Indices bac : 1..Longueur(S) (pas 0-based).

3. Recherche de sous-chaîne. On fait glisser une fenêtre de la longueur de P sur S ; la première position où la fenêtre coïncide avec P est renvoyée.

DEF FN ContientSousChaine(S, P : chaîne) : entier
Variables i, pos : entier
Début
  pos ← 0 ; i ← 1
  TantQue (pos = 0) ET (i ≤ Longueur(S) - Longueur(P) + 1) faire
    Si Sous_chaine(S, i, Longueur(P)) = P alors pos ← i FinSi
    i ← i + 1
  FinTantQue
  Retourner pos
Fin

Application : dans "INFORMATIQUE", la fenêtre de longueur 3 vaut "INF", "NFO", "FOR", "ORM", "RMA", puis "MAT" à la position 6. On retourne 6 ; pour "XYZ" on retournerait 0.

Équivalent Python (extrait).

def inverser(S):
    inv = ""
    for i in range(len(S)-1, -1, -1):
        inv = inv + S[i]
    return inv
print(inverser("INFORMATIQUE"))

Méthode / Automatismes
  • Inverser : boucle décroissante de Longueur(S) à 1, concaténer S[i] à la chaîne résultat.
  • Palindrome : comparer S à Inverser(S), ou vérifier S[i] = S[N-i+1] pour i de 1 à N div 2.
  • Occurrences d'un caractère : parcours linéaire, comparaison S[i] = c.
  • Recherche de sous-chaîne : boucle de 1 à Longueur(S) - Longueur(P) + 1, utiliser Sous_chaine.
  • Toujours initialiser la chaîne résultat à "" avant d'y concaténer.
Pièges classiques

Pièges fréquents : confondre indice 0-based et 1-based (le bac tunisien utilise 1-based) ; mal borner la boucle de recherche de sous-chaîne (borne haute : N - LP + 1) ; oublier que Longueur retourne le nombre de caractères, pas l'indice maximum.

Variantes rencontrées : compter les voyelles/consonnes ; supprimer les espaces d'une chaîne ; convertir une chaîne en majuscules à l'aide de Ord/Chr.