def table_bm(m):
    """construit la table de décalages de Boyer-Moore :
       d[j][c] est le plus grand k < j tel que m[k] == c,
       s'il existe, et n'est pas défini sinon"""
    d = [{} for _ in range(len(m))]
    for j in range(len(m)):
        for k in range(j):
            d[j][m[k]] = k
    return d

def decalage(d, j, c):
    """utilise la table d lorsque le caractère j est c
       au lieu du caractère attendu"""
    if c in d[j]:
        # c apparaît en d[j][c] et on décale de la différence
        return j - d[j][c]
    else:
        # c n'apparaît pas du tout dans m[0..j-1]
        return j + 1

def recherche(m, t):
    """affiche toutes les occurrences de m dans t
       avec l'algorithme de Boyer-Moore"""
    d = table_bm(m)
    i = 0
    while i <= len(t) - len(m):
        k = 0
        for j in range(len(m) - 1, -1, -1):
            if t[i + j] != m[j]:
                k = decalage(d, j, t[i + j])
                break
        if k == 0:
            print("occurrence à la position", i)
            k = 1
        i += k