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.