Compter les comparaisons

On ajoute un compteur incrémenté à chaque comparaison de caractères, en n'oubliant pas celle qui échoue : c'est une comparaison comme une autre.

def naive_comptee(texte, motif):
    n, m = len(texte), len(motif)
    comparaisons, positions = 0, []
    for i in range(n - m + 1):
        j = 0
        while j < m and texte[i + j] == motif[j]:
            j = j + 1
            comparaisons = comparaisons + 1
        if j < m:
            comparaisons = comparaisons + 1   # la comparaison qui echoue
        else:
            positions.append(i)
    return positions, comparaisons

def boyer_moore_comptee(texte, motif):
    n, m = len(texte), len(motif)
    dernier = table_mauvais_caractere(motif)
    comparaisons, positions, i = 0, [], 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and texte[i + j] == motif[j]:
            j = j - 1
            comparaisons = comparaisons + 1
        if j < 0:
            positions.append(i)
            i = i + 1
        else:
            comparaisons = comparaisons + 1
            i = i + max(1, j - dernier.get(texte[i + j], -1))
    return positions, comparaisons

print(naive_comptee("ONCHERCHECHAT", "CHAT"))        # ([9], 17)
print(boyer_moore_comptee("ONCHERCHECHAT", "CHAT"))  # ([9], 7)

Les deux algorithmes trouvent la même occurrence, mais l'un a lu $17$ fois un caractère du texte et l'autre $7$ fois. Sur un texte de plusieurs mégaoctets, ce rapport se traduit directement en secondes.