def table_sauts(motif , alphabet):  
    listeCar =  dict()
    for c in motif: 
        listeCar[c] = motif.index(c)
    return listeCar 
  
def BoyerMoore(seq, motif, alphabet): 
    m , s = len(motif) , len(seq)  
    listeCar = table_sauts(motif,alphabet)  
    p = 0
    while(p <= s - m): 
        j = m-1
        while ( j >= 0 ) and ( motif[j] == seq[p+j] ): 
            j -= 1

        if j < 0: 
            print( "Le motif a été trouvé en position {}".format(p) , end='.' ) 
            p += ( m - listeCar[ seq[p+m] ] if p+m < s else 1 ) 
        else: 
            p += max(1 , j - listeCar[ seq[p+j] ] ) 
  
sequence = 'ATAACAGAGAATAAGGCTAGAAATACTGAA'
motif = 'AGGCTA'
alphabet = 'ACTG'
BoyerMoore(sequence , motif , alphabet)
