TNSI : Cours Recherche dans un Texte : Algorithme de Boyer-Moore

Principe de l'Algorithme de Boyer-Moore

Python

Pour recherche si un motif m se trouve dans une chaîne c, on peut :

1. parcourir chaque caractère de la chaine c
2. si ce caractère correspond au premier caractère du motif m, alors on avance dans le motif tant que les caractères coïncident.
3. si on atteint la fin du motif, alors m se trouve dans c. Sinon on passe au caractère suivant de c.

Implémentation Python

def recherche(motif,chaine):
    lm,lc = len(motif), len(chaine)
    for i in range(lc-lm+1):
        i_motif,i_chaine = 0, i
        while i_motif < lm and chaine[i_chaine] == motif[i_motif]:
            i_motif += 1
            i_chaine += 1
        if i_motif == lm:
            return True
    return False

Étude du Coût de l'Algorithme de Boyer-Moore

Pte

Soient lm la longueur du motif et lc celle de la chaine, on vérifie que l'algorithme de recherche simple demande au plus lm(lc − lm + 1) comparaisons

Ex

Combien de comparaisons seront nécessaires si on recherche le motif bbbbbbbbba (neuf fois le caractère b suivi d'un a) dans une chaine contenant un million de b ?