Chaînes de caractères en Python : cours, algorithmes sur les textes et exercices corrigés

Q: Peut-on modifier une chaîne de caractères en Python ?

Non : une chaîne est immuable. `s[0] = "T"` provoque une `TypeError`, et `s.append(c)` une `AttributeError`, car `append` est une méthode des listes. Pour « modifier » une chaîne, on en construit une nouvelle avec des tranches et des concaténations, puis on lui donne le nom de l'ancienne : `s = "T" + s[1:len(s)]`. Pour un très long texte construit dans une boucle, on range les morceaux dans une liste et l'on recolle à la fin avec `"".join(L)` (en France, join est rappelé par le sujet qui s'en sert).

Q: Comment rechercher un mot dans une chaîne en Python ?

Par la recherche naïve d'un motif : le motif de longueur m apparaît en position i du texte de longueur n si `texte[i:i + m] == motif`. On essaie les positions de 0 à n - m, soit `for i in range(n - m + 1)` ; à chaque position, une boucle `while j < m and texte[i + j] == motif[j]` avance `j`, et si `j == m`, on renvoie `i`. Après la boucle, on renvoie -1, jamais `False`, puisque `False == 0` vaut `True`. Dans le `while`, le test de la borne vient en premier.

Q: Quelle est la complexité de la recherche naïve d'un motif ?

Au plus m(n - m + 1) comparaisons de caractères, pour un motif de longueur m dans un texte de longueur n : au plus m par position, et n - m + 1 positions. Ce maximum est atteint quand le texte n'a que des `a` et que le motif est fait de `a` suivis d'un seul `b` : pour n = 1000 et m = 10, 9 910 comparaisons. On écrit O(nm) au pire ; si m est voisin de n/2, le coût est quadratique en la longueur du texte. Au programme marocain, on donne aussi le meilleur cas : m comparaisons pour une occurrence en position 0.

Q: Comment tester si un mot est un palindrome en Python ?

Avec deux indices qui se rapprochent : `i = 0` et `j = len(s) - 1` ; tant que `i < j`, si `s[i] != s[j]`, on renvoie `False`, sinon on avance `i` et l'on recule `j`. Après la boucle, on renvoie `True`. La fonction fait au plus ⌊n/2⌋ comparaisons pour une chaîne de n caractères et s'arrête au premier désaccord ; j - i diminue de 2 à chaque tour. Construire la chaîne renversée puis comparer est plus simple à écrire, mais parcourt tout le texte. Au programme marocain, `s == s[::-1]` fait le test en une ligne.

Q: À quoi servent ord et chr en Python ?

`ord(c)` donne le code du caractère `c`, et `chr(k)` le caractère de code `k`. Les codes de `a` à `z` sont consécutifs, comme ceux de `A` à `Z` et de `0` à `9` : le rang d'une minuscule est `ord(c) - ord("a")`, de 0 à 25, et la lettre de rang k est `chr(ord("a") + k)`. C'est ainsi qu'on compte les fréquences des 26 lettres dans une liste de 26 compteurs, en un seul parcours du texte. En France, `ord` et `chr` sont hors de l'annexe du programme : un sujet qui s'en sert les rappelle.

Q: Comment programmer le chiffrement de César en Python ?

Ce chiffrement est au programme marocain. On numérote les lettres de `A` à `Z` de 0 à 25 ; la clé k remplace la lettre de rang r par la lettre de rang (r + k) bmod 26, soit `chr(ord("A") + (r + k) % 26)` avec `r = ord(c) - ord("A")`, et les autres caractères restent inchangés. Sans `% 26`, les dernières lettres sortent de l'alphabet. On déchiffre en décalant de 26 - k. Comme il n'y a que 26 clés, on casse César par force brute, ou par l'analyse des fréquences : la lettre la plus fréquente du message chiffré correspond très probablement au `E` en français.

Chaînes Python : codage des caractères, indexation, tranches, immuabilité, méthodes usuelles ; algorithmes sur les textes : comptage d'occurrences, recherche naïve d'un motif, palindromes, et pour le Maroc chiffrements de César et de Vigenère et compression RLE.

19méthodes
35exercices corrigés
6problèmes
20pièges
41figures

Les nombres sont ceux du chapitre complet ; chaque filière voit la partie qui correspond à son programme.

Une chaîne de caractères Python, de type str, est une suite de caractères indexée de 0 à len(s) - 1, qu'on lit par s[i] et qu'on découpe en tranches s[i:j], mais qu'on ne modifie jamais : elle est immuable, et l'on construit une nouvelle chaîne. Le chapitre traite ensuite les algorithmes sur les textes : comptage d'occurrences et fréquences des lettres, recherche naïve d'un motif, prouvée et en $O(nm)$ au pire, palindromes, comparaison de deux textes. Il est au programme d'informatique commune de première année en MPSI, PCSI, PTSI, TSI et TPC, au Maroc et en France ; le programme marocain y ajoute le chiffrement de César, celui de Vigenère et la compression RLE. Les exercices reprennent des questions des sujets du CNC, de CCINP, de Mines-Ponts, de X-ENS et de Banque PT.

Ce que tu sauras faire

Un texte, pour un programme, est une chaîne de caractères : une étiquette de caisse, une ligne de cahier, une séquence d'ADN, un message. Ce chapitre apprend à manipuler ces chaînes sans erreur d'indice, puis les algorithmes qui travaillent sur les textes, et d'abord la recherche d'un motif. À la fin de ce chapitre, tu dois savoir :

accéder à un caractère, extraire une tranche et dire combien elle contient de caractères ;
construire une nouvelle chaîne au lieu de modifier une chaîne, qui ne se modifie pas ;
comparer deux chaînes, passer d'un caractère à son code et revenir ;
découper un texte en morceaux et recoller des morceaux, en lisant la documentation donnée par l'énoncé ;
compter les occurrences d'un caractère et les fréquences des lettres en un seul parcours ;
écrire la recherche naïve d'un motif dans un texte, prouver qu'elle est juste et compter ses comparaisons ;
tester si un mot est un palindrome, comparer deux textes de même longueur.

L'essentiel : La recherche naïve Extrait gratuit

Un extrait de la fiche « L'essentiel » du chapitre. Les démonstrations sont dans le cours détaillé.

À retenir Positions, preuve, coût

Le motif apparaît en position $i$ si texte[i:i + m] == motif ; positions possibles : 0 à $n - m$ , soit range(n - m + 1).
Absent : on renvoie $-1$ , jamais False (False == 0 vaut True).
Dans le while, la borne d'abord : j < m and texte[i + j] == motif[j].
Les occurrences peuvent se chevaucher : "aa" est en 0, 1 et 2 dans "aaaa", alors que "aaaa".count("aa") vaut 2.
Terminaison : $m - j$ décroît dans le while, au plus $n - m + 1$ tours de for.
Invariants : texte[i:i + j] == motif[0:j] dans le while ; « aucune occurrence avant $i$ » dans le for.
Au plus $m(n - m + 1)$ comparaisons, atteint pour un texte de a et un motif de a terminé par un b : $O(nm)$ , quadratique si $m$ est de l'ordre de $n$ .

Une méthode du chapitre Extrait gratuit

Méthode Rechercher la première occurrence d'un motif

Quand l’utiliser

L'énoncé demande si un mot apparaît dans un texte, et où pour la première fois.

Rappel de cours

Recherche naïve : pour chaque position $i$ de 0 à $n - m$ , tester le motif en $i$ ; renvoyer la première position qui marche, et $-1$ si aucune ne marche.

Démarche

Calculer n = len(texte) et m = len(motif).
for i in range(n - m + 1) : les $n - m + 1$ positions.
Tester la position (méthode 9), et return i dès qu'elle marche.
Après la boucle, return -1.

Rédaction type

for i in range(n - m + 1):
    j = 0
    while j < m and texte[i + j] == motif[j]:
        j = j + 1
    if j == m:
        return i
return -1

« On essaie les $n - m + 1$ positions possibles dans l'ordre ; la première qui convient est renvoyée ; si aucune ne convient, on renvoie $-1$ . »

Exemple traité

print(cherche_motif("GC", "ATGCAGCT"))
print(cherche_motif("GG", "ATGCAGCT"))

Le programme affiche :

2
-1

Erreurs fréquentes

range(n - m) : la dernière position n'est jamais essayée.
return False pour « absent » : se confond avec la position 0, car False == 0 vaut True.
return -1 dans la boucle, après le premier essai.
Les correcteurs du concours CCINP (rapport 2021, filière PSI) notent que « la recherche d'un motif avec l'opérateur « in » ne semble pas connue » : quand l'énoncé le permet, m in t répond à « le motif apparaît-il ? », mais pas à « où ? ».

Pour s’entraîner

Exercices 9, 11, 12 et 15, problèmes 1 et 2.

Un exercice corrigé Extrait gratuit

Exercice Une recherche fausse à corriger ★☆☆

Voici deux fonctions écrites par des élèves. La première doit renvoyer True si mot (non vide) apparaît dans texte, la seconde la première position de mot dans texte, ou $-1$ .

def cherchermot_faux(mot, texte):
    # mot, texte : chaînes, mot non vide
    # devrait renvoyer True si mot apparaît dans texte
    n = len(texte)
    m = len(mot)
    for i in range(n - m + 1):
        j = 0
        while j < m - 1 and texte[i + j] == mot[j]:
            j = j + 1
        if j == m - 1:
            return True
    return False

def position_faux(mot, texte):
    # mot, texte : chaînes ; devrait renvoyer la
    # première position de mot dans texte, ou -1
    n = len(texte)
    m = len(mot)
    for i in range(n - m):
        j = 0
        while j < m and texte[i + j] == mot[j]:
            j = j + 1
        if j == m:
            return i
    return -1

Trouver pour chaque fonction un exemple où elle se trompe, et l'exécuter.
Expliquer chaque erreur et corriger chaque fonction.

Indications

Méthode 9 : la boucle intérieure doit pouvoir comparer les $m$ caractères du motif, et le succès se lit j == m.
Méthode 10 : les positions possibles vont de 0 à $n - m$ inclus, soit range(n - m + 1).

Analyse : comment trouver l’idée

Dans la première fonction, la condition j < m - 1 arrête la boucle avant de comparer le dernier caractère du motif : un motif qui diffère seulement par sa dernière lettre est déclaré présent. Dans la seconde, range(n - m) s'arrête à $n - m - 1$ : la dernière position, où le motif touche la fin du texte, n'est jamais essayée. On cherche donc un exemple qui vise exactement ces deux défauts.

Correction détaillée

print(cherchermot_faux("abd", "abc"))
print(position_faux("12", "0412"))
print(position_faux("0412", "0412"))

Le programme affiche :

True
-1
-1

'abd' n'apparaît pas dans 'abc', et '12' apparaît en position 2 de '0412', comme '0412' en position 0 : les trois réponses sont fausses.

Première fonction : quand $j$ atteint $m - 1$ , la boucle s'arrête sans comparer texte[i + m - 1] et mot[m - 1] ; le test j == m - 1 est alors vrai, que les derniers caractères soient égaux ou non. Seconde fonction : range(n - m) oublie la position $n - m$ ; quand le motif a la longueur du texte, la boucle ne tourne même pas. Corrections :

def cherchermot(mot, texte):
    # mot, texte : chaînes
    # renvoie True si mot apparaît dans texte
    n = len(texte)
    m = len(mot)
    for i in range(n - m + 1):
        j = 0
        while j < m and texte[i + j] == mot[j]:
            j = j + 1
        if j == m:            # les m caractères sont égaux
            return True
    return False

print(cherchermot("abd", "abc"), cherchermot("ab", "cab"))
print(cherche_motif("12", "0412"))
print(cherche_motif("0412", "0412"))

Le programme affiche :

False True
2
0

La seconde fonction corrigée, avec range(n - m + 1), est exactement cherche_motif du cours (section 8.3).

Interprétation : les deux erreurs ne se voient pas sur les tests « faciles » (motif au milieu du texte, motif très différent) ; il faut tester un motif qui diffère seulement par sa dernière lettre et un motif placé à la fin du texte.

Méthodes à retenir

Le succès d'une comparaison se lit j == m après une boucle while j < m and ... ; les positions vont jusqu'à $n - m$ inclus. Tester toujours la dernière lettre et la dernière position. Voir les méthodes 9 et 10.

Dans le chapitre complet

Le cours détaillé, toute la fiche « L'essentiel », 19 méthodes, 20 pièges corrigés, la carte mentale, 35 exercices corrigés, 6 problèmes de concours, les fiches à mémoriser et l'assistant qui répond à tes questions. Les trois premiers chapitres de chaque matière sont offerts avec un compte d’essai gratuit.

Ouvrir l'essai gratuit Une question ? WhatsApp

Plan du cours

1. Un texte est une suite de caractères
- 1.1 Le problème
- 1.2 Le type str
- 1.3 Longueur et indices
- 1.4 Tranches
2. Une chaîne ne se modifie pas
- 2.1 Immuabilité
- 2.2 Construire une nouvelle chaîne
- 2.3 Concaténation et répétition
- 2.4 Construire une chaîne dans une boucle
3. Comparer des chaînes
- 3.1 Égalité
- 3.2 Ordre lexicographique
- 3.3 Des nombres écrits en chaînes
4. Parcourir une chaîne
- 4.1 Par élément ou par indice
- 4.2 Compteur, accumulateur, drapeau
5. Les codes des caractères
- 5.1 Un code par caractère
- 5.2 Le rang d'une lettre
- 5.3 Au-delà des lettres latines
6. Fonctions et méthodes usuelles
- 6.1 Le test m in t
- 6.2 Découper et recoller : split et join
- 6.3 Les méthodes des chaînes
7. Compter dans un texte
- 7.1 Les occurrences d'un caractère
- 7.2 Les fréquences des 26 lettres
- 7.3 Les mots d'une phrase
8. Rechercher un motif dans un texte
- 8.1 Le problème
- 8.2 L'idée : une fenêtre qui glisse
- 8.3 Le code
- 8.4 Toutes les occurrences
- 8.5 Terminaison et correction
- 8.6 Combien de comparaisons ?
- 8.7 Cas limites
- 8.8 La version par tranches
9. Palindromes
- 9.1 Deux indices qui se rapprochent
- 9.2 Par renversement
- 9.3 Une phrase palindrome
10. Comparer deux textes de même longueur
- 10.1 La distance de Hamming
- 10.2 Anagrammes
11. Chiffrer un texte
- 11.1 Vocabulaire
- 11.2 Le chiffrement de César
- 11.3 Casser César
- 11.4 Le chiffrement de Vigenère
- 11.5 Coût
12. Compresser un texte : le codage RLE
- 12.1 Principe
- 12.2 Quand la RLE gagne, quand elle perd
- 12.3 Des usages réels

Les méthodes du chapitre

Chaque méthode est une fiche : quand l'utiliser, le rappel de cours, les étapes, la rédaction attendue sur la copie, un exemple traité, les erreurs à éviter.

Accéder à un caractère et extraire une tranche sans erreur d'indice
Modifier, c'est reconstruire
Choisir entre parcours par élément et parcours par indice
Construire une chaîne par accumulation
Passer d'un caractère à son code et revenir
Compter un caractère, puis les fréquences des 26 lettres
Comparer deux chaînes
Découper avec split et recoller avec join
Tester si un motif apparaît à une position donnée
Rechercher la première occurrence d'un motif
Rechercher toutes les occurrences
Prouver la recherche naïve
Compter les comparaisons et justifier $O(nm)$
Tester un palindrome avec deux indices
Comparer deux textes position par position ou par leurs lettres
Respecter les fonctions autorisées par un sujet
Chiffrer et déchiffrer avec César, casser par force brute ou par les fréquences
Chiffrer et déchiffrer avec Vigenère
Compresser et décompresser en RLE

Les exercices corrigés

Chaque exercice a ses indications, sa correction rédigée et ce qu'il faut en retenir.

Application directe (14)

Indices et tranches d'une adresse
De « Auttame » à « Automne »
Ce qu'on ne peut pas faire à une chaîne
Dates et noms de fichiers
Compter sans count
Majuscules et minuscules par les codes
Renverser des mots, tester un nombre
Les mots d'une phrase
Une recherche fausse à corriger
Deux versions d'un même texte
Une recherche à la main
Le caractère d'une trame GPS
César : chiffrer, déchiffrer, essayer toutes les clés
Vigenère

Entraînement (16)

Rechercher un mot et compter ses occurrences
Fréquences des lettres et des couples de lettres
Un drapeau et une position
Combien de comparaisons sur de l'ADN
Prouver la fenêtre glissante
Trames de géolocalisation
Anagrammes
Chaînes carrées et périodes
Une phrase palindrome
Le plus long préfixe commun
Le coût d'une concaténation répétée
Additionner de grands nombres écrits en chaînes
Un analyseur d'instructions
Opérations sur des mots binaires
Casser César par les fréquences
RLE dans un autre format

Approfondissement (5)

Justifier un paragraphe
Compresser avec un code de Huffman donné
Sauter plus loin : l'idée de Boyer-Moore-Horspool
Compter les facteurs palindromes
RSA sur les codes des caractères

Les problèmes de concours

Des extraits de sujets réels, corrigés en entier, avec la durée conseillée et les méthodes mobilisées.

Recherche d'un motif par la liste des suffixes
CNC 2018, filière PSI, épreuve d'informatique, partie III, questions 3 à 10
Rechercher un motif dans une séquence d'ADN
CCINP 2020, filière TSI, épreuve d'informatique, questions 1 à 13 et 17
Compter les caractères d'un texte
Mines-Ponts 2024, filières MP, PC et PSI, épreuve d'informatique commune, partie 1, questions 1 à 7
Décoder une trame GPS
CCINP 2021, filière PSI, épreuve d'informatique, partie I, questions 1, 2, 4 à 8 et 10
Le chiffrement de Vigenère et son cassage
CNC 2016, filières MP, PSI et TSI, épreuve d'informatique, problème II, questions 8 à 11 et 14 à 19
La transformée de Burrows-Wheeler, puis la compression RLE
CNC 2020, filière PSI, épreuve d'informatique, partie III, questions 1 à 6

Questions fréquentes

Peut-on modifier une chaîne de caractères en Python ?

Non : une chaîne est immuable. s[0] = "T" provoque une TypeError, et s.append(c) une AttributeError, car append est une méthode des listes. Pour « modifier » une chaîne, on en construit une nouvelle avec des tranches et des concaténations, puis on lui donne le nom de l'ancienne : s = "T" + s[1:len(s)]. Pour un très long texte construit dans une boucle, on range les morceaux dans une liste et l'on recolle à la fin avec "".join(L) (en France, join est rappelé par le sujet qui s'en sert).

Comment rechercher un mot dans une chaîne en Python ?

Par la recherche naïve d'un motif : le motif de longueur $m$ apparaît en position $i$ du texte de longueur $n$ si texte[i:i + m] == motif. On essaie les positions de 0 à $n - m$ , soit for i in range(n - m + 1) ; à chaque position, une boucle while j < m and texte[i + j] == motif[j] avance j, et si j == m, on renvoie i. Après la boucle, on renvoie $-1$ , jamais False, puisque False == 0 vaut True. Dans le while, le test de la borne vient en premier.

Quelle est la complexité de la recherche naïve d'un motif ?

Au plus $m(n - m + 1)$ comparaisons de caractères, pour un motif de longueur $m$ dans un texte de longueur $n$ : au plus $m$ par position, et $n - m + 1$ positions. Ce maximum est atteint quand le texte n'a que des a et que le motif est fait de a suivis d'un seul b : pour $n = 1000$ et $m = 10$ , 9 910 comparaisons. On écrit $O(nm)$ au pire ; si $m$ est voisin de $n/2$ , le coût est quadratique en la longueur du texte. Au programme marocain, on donne aussi le meilleur cas : $m$ comparaisons pour une occurrence en position 0.

Comment tester si un mot est un palindrome en Python ?

Avec deux indices qui se rapprochent : i = 0 et j = len(s) - 1 ; tant que i < j, si s[i] != s[j], on renvoie False, sinon on avance i et l'on recule j. Après la boucle, on renvoie True. La fonction fait au plus $\lfloor n/2 \rfloor$ comparaisons pour une chaîne de $n$ caractères et s'arrête au premier désaccord ; $j - i$ diminue de 2 à chaque tour. Construire la chaîne renversée puis comparer est plus simple à écrire, mais parcourt tout le texte. Au programme marocain, s == s[::-1] fait le test en une ligne.

À quoi servent ord et chr en Python ?

ord(c) donne le code du caractère c, et chr(k) le caractère de code k. Les codes de a à z sont consécutifs, comme ceux de A à Z et de 0 à 9 : le rang d'une minuscule est ord(c) - ord("a"), de 0 à 25, et la lettre de rang $k$ est chr(ord("a") + k). C'est ainsi qu'on compte les fréquences des 26 lettres dans une liste de 26 compteurs, en un seul parcours du texte. En France, ord et chr sont hors de l'annexe du programme : un sujet qui s'en sert les rappelle.

Comment programmer le chiffrement de César en Python ?

Ce chiffrement est au programme marocain. On numérote les lettres de A à Z de 0 à 25 ; la clé $k$ remplace la lettre de rang $r$ par la lettre de rang $(r + k) \bmod 26$ , soit chr(ord("A") + (r + k) % 26) avec r = ord(c) - ord("A"), et les autres caractères restent inchangés. Sans % 26, les dernières lettres sortent de l'alphabet. On déchiffre en décalant de $26 - k$ . Comme il n'y a que 26 clés, on casse César par force brute, ou par l'analyse des fréquences : la lettre la plus fréquente du message chiffré correspond très probablement au E en français.

Comment y accéder

Ce chapitre fait partie de l'accès complet. Les trois premiers chapitres de chaque matière (deux par bloc en économie et droit, en management et gestion) sont offerts avec un compte d'essai gratuit. Créer un compte d'essai ou se connecter. Pour l'accès complet, les tarifs ou une question, écris-nous sur WhatsApp.

Chaînes de caractères en Python : cours, algorithmes sur les textes et exercices corrigés

Ce que tu sauras faire

L'essentiel : La recherche naïve Extrait gratuit

Une méthode du chapitre Extrait gratuit

Un exercice corrigé Extrait gratuit

Plan du cours

Les méthodes du chapitre

Les exercices corrigés

Application directe (14)

Entraînement (16)

Approfondissement (5)

Les problèmes de concours

Questions fréquentes

Comment y accéder

Toute ta prépa au même endroit