L'algorithme de Boyer-Moore est un algorithme efficace pour la recherche de motifs dans une chaîne de caractères. Il utilise des heuristiques pour sauter plusieurs caractères lorsqu'une correspondance n'est pas trouvée, ce qui réduit le nombre total de comparaisons nécessaires.

Les principales étapes de l'algorithme de Boyer-Moore :

1. Prétraitement du motif : Le nœud supérieur de l'arbre.
2. Recherche du motif : Une fois que les tables de saut ont été construites, nous commençons la recherche en comparant le motif avec la chaîne de caractères à partir de la fin du motif. À chaque itération, nous décalons le motif en utilisant les informations des tables de saut pour sauter plusieurs caractères lorsque cela est possible.

Exemple de code Python illustrant l'implémentation de l'algorithme de Boyer-Moore :

def boyer_moore_search(text, pattern):
    n = len(text)
    m = len(pattern)

    # Construction des tables de saut
    bad_char = bad_character_table(pattern)
    good_suffix = good_suffix_table(pattern)

    # Recherche du motif dans le texte
    i = m - 1  # Indice pour le texte
    j = m - 1  # Indice pour le motif

    while i < n:
        if text[i] == pattern[j]:
            if j == 0:
                # Motif trouvé
                return i
            else:
                # Correspondance partielle, continuer la comparaison
                i -= 1
                j -= 1
        else:
            # Mauvais caractère, utiliser la table de décalage
            x = bad_char[ord(text[i])] if ord(text[i]) < 256 else -1
            y = good_suffix[j + 1]
            i += max(x, y)
            j = m - 1

    # Motif non trouvé
    return -1

def bad_character_table(pattern):
    table = [-1] * 256  # Table ASCII étendue

    for i in range(len(pattern)):
        table[ord(pattern[i])] = i

    return table

def good_suffix_table(pattern):
    m = len(pattern)
    suffixes = get_suffixes(pattern)
    border = get_border(pattern)

    table = [m - border[i] for i in range(m)]

    for i in range(m - 1):
        j = m - suffixes[i]
        if table[j] > border[i]:
            table[j] = border[i]

    return table

def get_suffixes(pattern):
    m = len(pattern)
    suffixes = [0] * m
    f = 0
    g = m - 1

    for i in range(m - 2, -1, -1):
        if i > g and suffixes[i + m - 1 - f] < i - g:
            suffixes[i] = suffixes[i + m - 1 - f]
        else:
            if i < g:
                g = i
            f = i
            while g >= 0 and pattern[g] == pattern[g + m - 1 - f]:
                g -= 1
            suffixes[i] = f - g

    return suffixes

def get_border(pattern):
    m = len(pattern)
    border = [0] * (m + 1)
    border[m] = m

    j = 0
    for i in range(m - 1, -1, -1):
        if is_prefix(pattern, i + 1):
            j = m - i - 1
        border[i] = j

    for i in range(1, m):
        suffix_len = get_suffix_len(pattern, i)
        if pattern[i - suffix_len] != pattern[m - 1 - suffix_len]:
            border[m - 1 - suffix_len] = m - i - 1

    return border


def is_prefix(pattern, p):
    m = len(pattern)
    j = 0

    for i in range(p, m):
        if pattern[i] != pattern[j]:
            return False
        j += 1

    return True


def get_suffix_len(pattern):
Voici la suite du code Python pour l'implémentation de l'algorithme de Boyer-Moore :

def get_suffix_len(pattern, p):
    length = 0
    j = len(pattern) - 1

    while p >= 0 and pattern[p] == pattern[j]:
        length += 1
        p -= 1
        j -= 1

    return length


# Exemple d'utilisation de la fonction de recherche
text = "La recherche textuelle est un sujet fascinant."
pattern = "textuelle"
result = boyer_moore_search(text, pattern)
if result != -1:
    print("Motif trouvé à l'indice", result)
else:
    print("Motif non trouvé")

Dans cet exemple, nous recherchons le motif "textuelle" dans la chaîne de caractères "La recherche textuelle est un sujet fascinant." Si le motif est trouvé, l'indice de la première occurrence est affiché. Sinon, un message indiquant que le motif n'a pas été trouvé est affiché.

Exercice 1: ★ ★ ★ ★ ☆

Écrire une fonction pour rechercher un motif dans une chaîne de caractères en utilisant l'algorithme de Boyer-Moore.
1. Implémentez la fonction recherche_motif(text, pattern) qui utilise l'algorithme de Boyer-Moore.
2. Testez votre fonction avec le texte "Bonjour le monde" et le motif "monde".

Exercice 2: ★ ★ ★ ★ ★

Modifiez l'algorithme de Boyer-Moore pour qu'il retourne toutes les occurrences d'un motif dans une chaîne de caractères.
1. Écrire une fonction toutes_occurrences(text, pattern) qui retourne une liste d'indices.
2. Testez votre fonction avec le texte "abcabcabc" et le motif "abc".

Exercice 3: ★ ★ ★ ☆ ☆

Écrivez une fonction pour détecter si un motif n'est pas présent dans une chaîne de caractères.
1. Écrire une fonction motif_absent(text, pattern) qui retourne True si le motif n'est pas trouvé, sinon False.
2. Testez votre fonction avec le texte "Hello World" et le motif "Python".

Exercice 4: ★ ★ ★ ★ ☆

Implémentez l'algorithme de Boyer-Moore et ajoutez des commentaires détaillés pour expliquer chaque étape.
1. Écrire une fonction implémentation_boyer_moore(text, pattern) avec des commentaires.
2. Testez votre fonction avec le texte "Recherche de motifs" et le motif "mots".

Exercice 5: ★ ★ ★ ★ ★

Créez un programme qui recherche plusieurs motifs dans une chaîne de caractères donnée.
1. Écrire une fonction recherche_multiples(text, patterns) qui retourne un dictionnaire avec les motifs comme clés et leurs indices comme valeurs.
2. Testez votre fonction avec le texte "Test de recherche" et les motifs ["Test", "recherche", "non trouvé"].