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 (si demandée) : pour i de 1 à Longueur(S)-Longueur(P)+1, comparer Sous_chaine(S,i,Longueur(P)) à P.

Équivalent Python (extrait).
```python
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`.