Aller au contenu

Exercices — Recherche textuelle

1. QCM

  1. Quelle est la complexité de la recherche d'un caractère dans un texte de longueur n ?

a. O(1)

b. O(n)

c. O(n²)

  1. Dans l'algorithme de recherche naïve, si le texte a une longueur n et le motif une longueur m, combien de positions de départ sont testées au maximum ?

a. n

b. n - m

c. n - m + 1

  1. Quelle est la particularité de l'algorithme de Boyer-Moore par rapport à la recherche naïve ?

a. Il compare les caractères de gauche à droite

b. Il compare les caractères de droite à gauche

c. Il ne fait aucune comparaison

  1. À quoi sert le pré-traitement du motif dans l'algorithme de Morris-Pratt ?

a. À trier les caractères du motif

b. À calculer les décalages optimaux après un échec

c. À compter le nombre de caractères différents

  1. Dans le pire cas, quelle est la complexité de l'algorithme de recherche naïve ?

a. O(n)

b. O(m)

c. O(n × m)

2. Questions de cours

Question 1

On considère le texte "abracadabra" et le motif "abra".

a. Combien de positions de départ sont testées par l'algorithme naïf ?

b. À quelles positions le motif est-il trouvé ?

Question 2

Expliquez pourquoi l'algorithme de Boyer-Moore peut être plus efficace que la recherche naïve, notamment quand le motif est long.

Question 3

On considère le code suivant :

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

a. Que renvoie recherche("bonjour", "jour") ?

b. Que renvoie recherche("bonjour", "soir") ?

c. Modifiez la fonction pour qu'elle renvoie toutes les positions où le motif apparaît (sous forme de liste).

3. Exercices de programmation

Exercice 1 : Compter les occurrences

Écrire une fonction compter_occurrences(texte, motif) qui renvoie le nombre de fois où le motif apparaît dans le texte.

>>> compter_occurrences("abracadabra", "a")
5
>>> compter_occurrences("abracadabra", "abra")
2

Exercice 2 : Recherche insensible à la casse

Écrire une fonction recherche_insensible(texte, motif) qui effectue une recherche en ignorant les majuscules/minuscules.

>>> recherche_insensible("Bonjour tout le Monde", "monde")
16
>>> recherche_insensible("PYTHON", "python")
0

Exercice 3 : Analyse de complexité

On exécute la recherche naïve avec le texte "aaaaaaaaaa" (10 fois 'a') et le motif "aaab".

a. Combien de comparaisons sont effectuées au total ?

b. Expliquez pourquoi ce cas est défavorable pour l'algorithme naïf.

Exercice 4 : Table des dernières occurrences (Boyer-Moore)

Pour l'algorithme de Boyer-Moore, on construit une table indiquant la dernière position de chaque caractère dans le motif.

Pour le motif "EXEMPLE", construire cette table.

Auteur : Florian Mathieu

Licence CC BY NC

Licence Creative Commons
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.