cours/c17c.md

Résumé cours

Ce qu’il faut savoir

• les algorithmes permettant de rechercher un motif (suite de lettres) dans un texte ont une grande importance en informatique

• L'algorithme de Boyer-Moore effectue un prétraitement du motif. Cela signifie que l'algorithme "connait" les caractères qui se trouvent dans le motif

• Dans l'algorithme de Boyer-Moore on commence la comparaison motif-chaine par la droite du motif. Par exemple pour le motif CGGCAG, on compare d'abord le G, puis le A, puis C...on parcourt le motif de la droite vers la gauche

• Dans le cas de l'algorithme "naïf", les décalages du motif vers la droite se faisaient toujours d'un "cran" à la fois. L'intérêt de l'algorithme de Boyer-Moore, c'est qu'il permet, dans certaines situations, d'effectuer un décalage de plusieurs crans en une seule fois.

• plus le motif est grand et plus l'algorithme de Boyer-Moore sera efficace par rapport à l'algorithme "naïf"

Ce qu’il faut savoir faire

Vous devez être capable d'appliquer l'algorithme de Boyer-Moore sur un cas simple.

Exemples d'activités

activité 17.1

Voici la première strophe du poème de Paul Verlaine Chanson d'automne :

Les sanglots longs
Des violons
De l'automne
Blessent mon coeur
D'une langueur
Monotone.

1. Recherchez le motif uto dans cette strophe en utilisant l'algorithme de Boyer-Moore

2. Recherchez le motif ail dans cette strophe en utilisant l'algorithme de Boyer-Moore

activité 17.2

La fonction recherche ci-dessous :

def recherche(txt, motif):
    NO_CAR = 256
    m = len(motif)
    n = len(...)
    tab_car = [-1]*NO_CAR
    for i in range(...):
        tab_car[ord(motif[i])] = i
    decalage = 0
    res = ...
    while(decalage <= n-m):
        j = m-1
        while j>=0 and motif[j] == txt[decalage+j]:
            j = j - 1
        if j<0:
            res.append(decalage)
            if decalage+m<n :
                decalage = decalage + m-tab_car[ord(txt[decalage+m])]
            else :
                decalage = decalage + 1
        else:
            decalage = decalage + max(1, j-tab_car[ord(txt[decalage+j])])
    return res

permet de trouver la position du motif motif dans le texte txt. Si le motif motif est présent dans texte txt, la fonction recherche renvoie un tableau contenant les indices de positions du motif dans le texte. Dans le cas où le motif n'est pas présent, la fonction recherche renvoie un tableau vide.

Par exemple recherche("AZERTYAZER", "ER") renverra le tableau [2,8], recherche("AZERTYAZER", "AB") renverra le tableau [ ].

Après avoir étudié attentivement cette fonction recherche, vous compléterez cette fonction (remplacez les ...) pour qu'elle fournisse les résultats attendus.