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.

Ce qui aide à reconnaître la démarche

« É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 »

Besoin d’un point de départ ? Voir la méthode

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.

Les pièges à vérifier dans ta démarche

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.

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.

É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.
É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".
É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"))

Changer d’énoncé, garder le raisonnement

Choisis un seul transfert après le sujet principal. Qu’est-ce qui change ? Quel résultat ou quelle méthode peux-tu réutiliser ? Les autres exercices restent disponibles pour une prochaine séance.

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.

Exercices d'entraînement — une nuance à la fois

1 Compter des sous-chaînes qui se chevauchent

Entraînement 01 / 01

Compter des sous-chaînes qui se chevauchent

1 questionCorrigé masquéEn cours de relecture

On travaille sur deux chaînes de caractères S et P, avec 1 ≤ Long(P) ≤ Long(S) ≤ 80. Les indices commencent à 1. Sous_chaine(S,i,k) retourne exactement k caractères à partir de i. Deux occurrences du motif P peuvent se chevaucher : elles comptent alors séparément. Ainsi, chercher toutes les occurrences diffère de chercher seulement la première.

Écrire la fonction NbMotifs(S,P) qui retourne le nombre de positions de départ du motif P dans S, et son TDOL (objets, types et rôles). Construire ensuite la trace de toutes les fenêtres testées pour S = "ABABABA" et P = "ABA". Expliquer pourquoi avancer de Long(P) après une correspondance ne respecte pas la consigne.

Cet exercice et sa correction sont en cours de relecture. Tu peux les consulter ; l’exercice n’est pas encore proposé en séance.

Voir la correction commentéeAprès avoir posé votre démarche

TDOL. i : entier, indice de départ de la fenêtre ; n : entier, nombre de caractères de S ; k : entier, nombre de caractères du motif ; compteur : entier, nombre d’occurrences rencontrées. S et P sont les paramètres chaînes en entrée ; la fonction retourne un entier.

0) DEF FN NbMotifs(S,P : chaîne) : entier
1) n ← Long(S) ; k ← Long(P) ; compteur ← 0
2) Pour i de 1 à n-k+1 faire
     Si Sous_chaine(S,i,k) = P alors
       compteur ← compteur+1
     FinSi
   FinPour
3) NbMotifs ← compteur
4) Fin NbMotifs

Trace.

i	Fenêtre de longueur 3	compteur après le test
1	ABA	1
2	BAB	1
3	ABA	2
4	BAB	2
5	ABA	3

On retourne 3. La borne 7−3+1 = 5 garantit que la dernière fenêtre reste entièrement dans S.

Après la correspondance à i=1, un saut de 3 conduit à i=4 : l’occurrence à i=3 est perdue. Le pas doit rester égal à 1, même après un succès ; chaque position possible est alors examinée une fois. Les contraintes excluent le motif vide, dont le comptage demanderait une convention différente.

Relier ce raisonnement au bac

Choisis une filière pour voir les sujets qui étayent ce scénario.

Tu écris. Tu continues.