exo 3.5

"Exercice 3.5: Motifs chevauchants"
# prend une sequence et une liste de motifs
# retourne la liste des frequences d'occurence de chaque motif avec chevauchement
def overlapping_motifs(seq, motifs):
    # initialise la liste vide des frequences a retourner
    freqs = []
    # traitement a effecture une fois par motif pour remplir la liste de frequences
    for motif in motifs:
        #####################################################
        #1# calcul du nombre effectif d'occurences du motif #
        #####################################################
    start_idx  = 0 # indice du caractere a partir duquel commencer a chercher
        occurences = 0 # accumulateur contant le nombre total d'occurence du motif courrant
    fini = False   # drapeau indiquant si la sequence a ete totalement exploree
        # tant que la frequence n'est pas totalement exploree
    while not fini:
            # start_idx contient l'index a partir duquel chercher
            found = seq.find(motif, start_idx) # chercher le motif
            # find retourne l'index auquel le motif a ete trouve
        if found >= 0:
                # nouvel indice ou chercher (immediatement apres la derniere occurence du motif)
                start_idx = found + 1
                # incrementer le nombre d'occurences trouvees
                occurences += 1
            # si find ne trouve rien (retourne -1)
            else:
                fini = True # activer le drapeau

        #######################################################
        #2# calcul du maximum potentiel d'occurences du motif #
        #######################################################
        max_occurences = 0 # initialiser l'accumulateur a 0
        # implementation de la formule de l'enonce
        # /!\ dans l'enonce, la fonction plancher devrait etre appliquee /!\
        # /!\ aux termes de la somme, et non a la somme elle meme        /!\
        for i in range (0, len(motif)):
            max_occurences += math.floor((len(seq) - i)/float(len(motif)))

        #####################################################################
        #3# calcul de la frequence d'apparition du motif avec chevauchement #
        #####################################################################
        # calcul de la frequence et ajout a la liste des frequences a retourner
        freqs.append(occurences/float(max_occurences))

    # retour de la liste remplie
    return freqs