Algorithme Boyer-Moore : comparaison des coûts

In [1]: cout(motif, texte)

Coût : algorithme naïf
Nombre de caractères du texte :  120000
Nombre de caractères du motif :  20
Durée de la recherche (s) :  0,18181410000033793

Coût : algorithme Boyer-Moore
Nombre de caractères du texte :  120000
Nombre de caractères du motif :  20
Durée de la recherche (s) :  0,002768899999864516

from time import perf_counter
from module_boyer_moore import *

# implémentation de l'algorithme naïf
def recherche(m, t):
    lt = len(t)
    lm = len(m)
    lp = []
    for p in range(lt - lm + 1):
        s = ''
        for car in range(p, p + lm):
            s = s + t[car]
        if s == m :
            lp.append(p)
    return lp

def cout(motif, texte):
    debut_rech = perf_counter()
    recherche(motif,texte)
    fin_rech = perf_counter()
    duree_execution = (fin_rech - debut_rech)
    duree_execution = str(duree_execution).replace(".", ",")
    print("\nCoût : algorithme naïf")
    print("Nombre de caractères du texte : ", len(texte))
    print("Nombre de caractères du motif : ", len(motif))
    print("Durée de la recherche (s) : ", duree_execution)
    
    debut_rech = perf_counter()
    recherche_bm(motif,texte)
    fin_rech = perf_counter()
    duree_execution = (fin_rech - debut_rech)
    duree_execution = str(duree_execution).replace(".", ",")
    print("\nCoût : algorithme Boyer-Moore")
    print("Nombre de caractères du texte : ", len(texte))
    print("Nombre de caractères du motif : ", len(motif))
    print("Durée de la recherche (s) : ", duree_execution)

texte = "a" * 120000
motif = "z" * 20