def recherche(motif, chaine):
    # Calculer les longueurs du motif et de la chaîne
    lm, lc = len(motif), len(chaine)
    
    # Parcourir la chaîne principale
    for i in range(lc - lm + 1):
        # Initialiser les indices pour parcourir le motif et la sous-chaîne
        i_motif, i_chaine = 0, i
        
        # Comparer les caractères du motif avec ceux de la sous-chaîne
        while i_motif < lm and chaine[i_chaine] == motif[i_motif]:
            i_motif += 1
            i_chaine += 1
        
        # Si tous les caractères du motif correspondent, retourner True
        if i_motif == lm:
            return True
    
    # Si aucun motif correspondant n'est trouvé, retourner False
    return False

# Tester la fonction avec quelques assertions
assert recherche("abc", "abcdefg") == True  # Le motif "abc" est présent dans la chaîne "abcdefg"
assert recherche("xyz", "abcdefg") == False # Le motif "xyz" n'est pas présent dans la chaîne "abcdefg"
assert recherche("hello", "hello world") == True # Le motif "hello" est présent dans la chaîne "hello world"
assert recherche("world", "hello world") == True # Le motif "world" est présent dans la chaîne "hello world"
assert recherche("foo", "bar") == False # Le motif "foo" n'est pas présent dans la chaîne "bar"

print("Tous les tests ont réussi!") # Affiche un message si tous les tests réussissent

Le Fonctionnement de l'Algorithme de Boyer-Moore

L'algorithme de Boyer-Moore est un algorithme de recherche de sous-chaîne particulièrement efficace. Voici une explication simplifiée :

1. Principe de l'Algorithme de Boyer-Moore:
   • L'objectif est de rechercher un motif (une séquence de lettres) dans un texte plus long.
   • Plutôt que de parcourir chaque caractère du texte un par un, Boyer-Moore effectue un prétraitement du motif.
   • Ce prétraitement permet à l'algorithme de "connaître" les caractères présents dans le motif et d'optimiser la recherche.
2. Vérification à l'envers:
   • On aligne le motif sous la chaîne de texte, en partant de la gauche.
   • On compare les lettres du motif avec celles correspondantes de la chaîne, mais en partant de la fin du motif (ce qui peut sembler contre-intuitif).
   • Si une non-correspondance est détectée, l'algorithme utilise des tables de sauts pour sauter certaines positions dans le texte.
   • L'objectif est de minimiser le nombre de comparaisons nécessaires pour trouver le motif.
3. Tables de sauts:
   • L'algorithme utilise deux tables de sauts :
     • La première table associe à chaque lettre de l'alphabet la distance depuis la fin du motif jusqu'à la dernière occurrence de cette lettre dans le motif.
     • La seconde table stocke des informations sur la position la plus à droite de chaque caractère du motif à partir d'un indice donné.
   • Ces tables permettent d'améliorer l'efficacité de la recherche.
4. Coût de l'Algorithme de Boyer-Moore:
   • En comparaison avec les méthodes de recherche basiques, l'algorithme de Boyer-Moore peut effectuer la recherche en un temps sous-linéaire.
   • Le nombre de comparaisons dépend de la longueur du motif et de la chaîne de texte.

L'algorithme de Boyer-Moore repose sur le principe de la recherche en décalage, c'est-à-dire qu'il utilise des règles de décalage pour éviter de vérifier inutilement des correspondances déjà exclues. Voici comment il fonctionne :

• Il commence par la fin du motif et cherche dans le texte la première occurrence du dernier caractère du motif. Si ce dernier caractère est présent dans le texte, on compare les caractères du motif en partant de la fin jusqu'à trouver une différence.
• Si une différence est trouvée, l'algorithme utilise les règles de décalage pour sauter des positions dans le texte en vue du prochain essai de correspondance.

Les règles de décalage utilisées dans l'algorithme de Boyer-Moore sont les suivantes :

1. Si le caractère du texte qui ne correspond pas au motif ne figure pas dans le motif, on décale le motif jusqu'à ce que le dernier caractère du motif coïncide avec le caractère suivant dans le texte.
2. Si le caractère du texte qui ne correspond pas au motif figure dans le motif, on décale le motif jusqu'à ce que le dernier caractère du motif coïncide avec ce caractère dans le texte.
3. Si le caractère du texte qui ne correspond pas au motif figure dans le motif, mais il n'y a pas de correspondance possible entre les caractères précédents, on décale le motif d'un nombre de caractères égal à la longueur du motif.

Ces règles de décalage permettent de sauter des positions dans le texte pour éviter de vérifier inutilement des correspondances déjà exclues, ce qui rend l'algorithme de Boyer-Moore très efficace.

Exemple d'application de l'algorithme de Boyer-Moore

Voici un exemple simple d'application de l'algorithme de Boyer-Moore pour la recherche du motif "a b c" dans le texte "a b a c b d a b r a b c a".

Tout d'abord, on construit les tableaux de saut de prétraitement "d" pour le motif "abc":

Ensuite, on commence la recherche à partir de la position 0 du texte. On compare les caractères du motif et du texte de droite à gauche, en commençant par la fin du motif.

Texte :    a b a c b d a b r a b c a
Motif :    a b c

• À la position 2, on compare le caractère "c" du motif et le caractère "a" du texte. Comme ils ne correspondent pas, on utilise le tableau de saut "d" pour déterminer le nombre de positions à sauter.

  Copier le code

  Texte :    a b a c b d a b r a b c a
  Motif :            a b c

  Le caractère "a" du texte est pas présent dans le motif, donc on saute 2 positions à droite, ce qui nous amène à la position 4.

• À la position 4, on compare le caractère "c" du motif et le caractère "b" du texte. Comme ils ne correspondent pas, on utilise à nouveau le tableau de saut "d".

  Copier le code

  Texte :    a b a c b d a b r a b c a
  Motif :                a b c

  Le caractère "b" du texte est présent dans le motif, donc on saute 1 position à droite, ce qui nous amène à la position 5.

• À la position 5, on compare le caractère "c" du motif et le caractère "d" du texte. Comme ils ne correspondent pas, on utilise le tableau de saut "d".

  Copier le code

  Texte :    a b a c b d a b r a b c a
  Motif :                   a b c

  Le caractère "d" du texte n'est pas présent dans le motif, donc on saute 3 position à droite, , ce qui nous amène à la position 8.

• À la position 8, on compare le caractère "c" du motif et le caractère "r" du texte. Comme ils ne correspondent pas, on utilise le tableau de saut "d".

  Copier le code

  Texte :    a b a c b d a b r a b c a
  Motif :                                  a b c

  Le caractère "r" du texte n'est pas présent dans le motif, donc on saute 3 position à droite, , ce qui nous amène à la position 11.

• À la position 11, on compare le caractère "c" du motif et le caractère "c" du texte. Comme ils correspondent, on continue à comparer les caractères précédents.

  Copier le code

  Texte :    a b a c b d a b r a b c a
  Motif :                                    a b c

• À la position 10, on compare le caractère "b" du motif et le caractère "b" du texte. Comme ils correspondent, on continue à comparer les caractères précédents.

• À la position 9, on compare le caractère "a" du motif et le caractère "a" du texte. Comme ils correspondent, on a trouvé une occurrence du motif à la position 5.

L'algorithme s'arrête ici, car on a trouvé une occurrence du motif dans le texte.

Unoutil en ligne (mise en ligne par L. Abdal, d'après un travail de N. Reveret), permet de visualiser un algorithme dit de "recherche naïve".

def boyer_moore(texte, cle):
    long_txt = len(texte)
    long_cle = len(cle)
    positions = []  # Liste pour stocker les positions des occurrences

    if long_cle <= long_txt:
        decalage = table_sauts(cle)  # Prétraitement : création de la table de sauts

        i = 0
        trouve = False
        while i <= long_txt - long_cle:
            for j in range(long_cle - 1, -1, -1):
                trouve = True
                if texte[i + j] != cle[j]:
                    # Si le caractère ne correspond pas, on ajuste le décalage
                    if texte[i + j] in decalage and decalage[texte[i + j]] <= j:
                        i += decalage[texte[i + j]]
                    else:
                        i += j + 1
                    trouve = False
                    break
            if trouve:
                positions.append(i)  # On a trouvé une occurrence, on la stocke
                i += 1
                trouve = False
        return positions  # Renvoie la liste des positions des occurrences

# Fonction pour créer la table de sauts
def table_sauts(cle):
    decalage = {}
    long_cle = len(cle)
    for i in range(long_cle - 1):
        decalage[cle[i]] = long_cle - i - 1
    return decalage

# Exemple d'utilisation
texte = "ABCDABEABC"
cle = "ABC"
resultats = boyer_moore(texte, cle)
print("Occurrences de la clé dans le texte aux positions :", resultats)