Algorithme de Boyer-Moore : fonction de calcul du décalage du motif.

Les arguments de la fonction sont :

• l’index du caractère du motif qui est comparé à celui du texte ;
• le caractère du texte qui est comparé à celui du motif ;
• la table de décalage

La fonction n’est appelée qui si un caractère du texte diffère du caractère du motif qui lui fait face (d’index ‘id’).

On cherche alors à savoir si ce caractère du texte figure parmi les caractères du motif qui précèdent celui qui lui fait face.

Deux cas se présentent :

1 – le caractère du texte ne figure pas parmi les caractères du motif qui précèdent celui qui lui fait face : la fonction renvoie alors ‘id’ + 1

2 – le caractère du texte figure parmi les caractères du motif qui précèdent celui qui lui fait face : on lit la valeur ‘vid’ de l’index de ce caractère dans la table de décalage et la fonction renvoie ‘id’ – ‘vid’

def val_decal(tdd : list, idc : int ,car : str) -> int :
    """ Détermine la valeur du décalage du motif dans l'algorithme
    de Boyer-Moore, lorsque le caractère du texte 'car' est différent
    de celui du motif d'index 'idc'.
    
    Pré-conditions
    >>> 'tdd' : table de décalage, liste de dictionnaires
    >>> 'idc ' : index du caractère dans le motif, entier positif,
        supérieur ou égal à zéro, strictement inférieur au nombre de 
        caractères du motif
    >>> 'car' : caractère du texte en face du caractère du motif, str : une
        seule lettre

    Post-conditions
    >>> renvoie un entier positif compris entre 1 et la longueur du motif,
        inclus.
    """

    # On consulte le dictionnaire situé à l'index 'idc' dans la table 
    # de décalage
    
    # Cas 1 - le caractère du texte est une des clés du dictionnaire
    if car in tdd[idc]:

        # on renvoie une valeur de décalage calculée à partir
        # de la valeur de index et de la valeur associée à la clé 'car'
        return idc - tdd[idc][car]
    
    # Cas 2 - le caractère du texte n'est pas une des clés du dictionnaire
    return idc + 1

Auto-évaluation