C17.1 : Algorithme naïf

Présentation

Considérons deux chaines de caractères : un Texte T et un motif M

On souhaite déterminer si M est présent dans T, ainsi que les positions correspondantes.

Remarque :

Il s'agit ici de reprogrammer la fonction, donc sans utiliser :

  • - le test d'appartenance in,
  • - la méthode index des chaines de caractères,
  • - l'extractin d'une sous-chaine d'une chaine avec les slices [ : ].

Algorithme naïf

1) Proposer une fonction recherche_naif(M:str, T:str)->list qui permet de répondre à l'objectif.

2) Estimer, dans le pire cas, le coût de votre algorithme en fonction de la longueur t de T et m de M.

Quelques petites variantes possibles

Commencer par le dernier caractère de M

1) Améliorer le code précédant en commençant la comparaison des lettres du motif avec les lettres du texte par la fin du motif.

2) Quel est l'amélioration sur le coût de cette nouvelle version ?

Cas où l'on ne recherche que la première occurrence

Proposer une nouvelle version recherche_occ1_naif(M:str, T: str) -> int de la fonction qui renvoie un entier correspondant à la position de la première occurrence de M dans T ou None si M n'est pas dans T.