Terminale · Numérique et sciences informatiques

Découvrir la recherche textuelle : chercher un motif dans un texte

Expliquer le problème de la recherche d'un motif dans un texte, décrire l'algorithme naïf par comparaisons successives et justifier pourquoi un automate fini permet d'éviter des comparaisons répétées.

Aperçu gratuit
Illustration de la fiche « Découvrir la recherche textuelle : chercher un motif dans un texte »

Les points essentiels

  • La recherche textuelle consiste à déterminer si un motif (chaîne de longueur m) apparaît dans un texte (chaîne de longueur n) et, si oui, à quelle position (indice du premier caractère de l'occurrence).
  • Le motif et le texte sont des mots sur un même alphabet fini (lettres, chiffres, bases A, C, G, T d'un brin d'ADN...). Les positions se comptent à partir de 0 avec les indices Python.

Les mots à connaître

Motif
Chaîne de caractères de longueur m que l'on cherche dans un texte plus long. Une occurrence du motif en position i signifie que texte[i:i+m] est égal au motif.
Recherche textuelle
Problème algorithmique : étant donné un texte de longueur n et un motif de longueur m, déterminer s'il existe au moins une occurrence du motif et, selon l'énoncé, renvoyer la première position, toutes les positions ou leur nombre.

Un exemple pour comprendre

Avec l'algorithme naïf, recherchez le motif « ABA » dans le texte « CABABA » (indices à partir de 0). Donnez toutes les positions d'occurrence et le nombre total de comparaisons de caractères.

Texte : C A B A B A (indices 0 à 5), motif ABA (m = 3), n = 6, donc positions testées : i = 0, 1, 2, 3. i = 0 : on compare 'C' et 'A' : différent, 1 comparaison. i = 1 : 'A'='A' (ok), 'B'='B' (ok), 'A'='A' (ok) : motif trouvé en position 1, 3 comparaisons. i = 2 : 'B' contre 'A' : différent, 1 comparaison. i = 3 : 'A'='A', 'B'='B', 'A'='A' : occurrence en position 3, 3 comparaisons. Bilan : occurrences aux positions 1 et 3 (elles se chevauchent sur le A de l'indice 3), total 1 + 3 + 1 + 3 = 8 comparaisons.

Première page de l’Essentiel : Découvrir la recherche textuelle : chercher un motif dans un texte
Ketty