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. On s'intéresse au pire cas.

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

2.b. Donner un exemple de pire cas.

1.

L'algorithme proposé utilise un boucle while de façon à ne pas parcourir tout le motif (on aurait pu utiliser une fonction "recherche caractère" avec une boucle for et un return qui fait sortir de la boucle).

Les indices utilisés sont représentés sur le schéma ci-dessous :

def recherche(M: str, T: str) -> list:
    """
    Exemples
    >>> recherche('Bon', 'Hello !')
    []
    >>> recherche('Bon', 'Bonjour !')
    [0]
    >>> recherche('Bon', 'Bonjour. Bonne année !')
    [0, 9]
    >>> recherche('bon', 'Ce gâteau est très bon')
    [19]
    """
    m = len(M)
    t = len(T)
    res = []
    for i_T in range(t - m + 1):
        i_M = 0
        while M[i_M] == T[i_T + i_M] and i_M < m - 1 :
            i_M = i_M + 1
        if M[i_M] == T[i_T + i_M]:
            res.append(i_T)
    return res

if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose = True)

2.a.

Dans tous les cas, la boucle for est exécutée \(1-m+1\) fois.

Et dans le pire cas, la boucle while est exécutée \(m\) fois.

Le coût est donc \(O(m)\)

2.b.

Voici un exemple de pire cas pour cet algorithme : M = "aaaaaaaaaa" et T = "aaab".

Quelques petites variantes possibles

Commencer par le dernier caractère de M

1. Modifier le code précédent en commençant la comparaison des lettres du motif avec les lettres du texte par la fin du motif.

2.a. Le coût de cette nouvelle version, dans le pire cas, est-il amélioré ?

2.b. Donner un exemple de pire cas pour cet algorithme.

1.

def recherche(M: str, T: str) -> list:
    """
    Exemples
    >>> recherche('Bon', 'Hello !')
    []
    >>> recherche('Bon', 'Bonjour !')
    [0]
    >>> recherche('Bon', 'Bonjour. Bonne année !')
    [0, 9]
    >>> recherche('bon', 'Ce gâteau est très bon')
    [19]
    """
    m = len(M)
    t = len(T)
    res = []
    for i_T in range(t - m + 1):
        i_M = m - 1
        while M[i_M] == T[i_T + i_M] and i_M > 0 :
            i_M = i_M - 1
        if M[i_M] == T[i_T + i_M]:
            res.append(i_T)
    return res

if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose = True)

2.a.

Le coût est le même m : \(O(m)\)

2.b.

Voici un exemple de pire cas pour cet algorithme : M = "aaaaaaaaaa" et T = "baaa".

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.