Algorithme de Boyer-Moore : fonction de création d’une table de décalage

Implémentation en langage Python

def table_decal(motif):
    """ Fonction qui construit une table de décalage (algorithme de Boyer-Moore) 
    pour un 'motif' donné.
    
    Pré-conditions :
    - motif est un argument de type string, non vide
    
    Post-conditions :
    - renvoyer une liste de dictionnaires, un élément d'un dictionnaire est 
    constitué d'une clé (key) qui est une lettre du motif et d'une valeur 
    qui est son index dans le motif.
    
    Par exemple :
        In [1]: table_decal("chercher")
        Out[1]: 
        [{},
         {'c': 0},
         {'c': 0, 'h': 1},
         {'c': 0, 'h': 1, 'e': 2},
         {'c': 0, 'h': 1, 'e': 2, 'r': 3},
         {'c': 4, 'h': 1, 'e': 2, 'r': 3},
         {'c': 4, 'h': 5, 'e': 2, 'r': 3},
         {'c': 4, 'h': 5, 'e': 6, 'r': 3}]
    """
    
    table_decalage = []
    for i in range (len(motif)):
        # ajout d'un dictionnaire vide pour chaque caractère de 'motif' 
        table_decalage.append({})
        for j in range (i):
            # [motif[j] : caractère de 'motif' qui sert de clé
            table_decalage[i][motif[j]] = j

    return table_decalage

Auto-évaluation