Problème — Un chercheur de motif, dans les trois paradigmes

1. Le prétraitement produit une donnée — la table — qui dépend du motif et de lui seul, et qui doit survivre entre deux recherches. C'est exactement la définition d'un état attaché à une entité durable : un objet. En impératif pur, il faudrait passer la table en argument à chaque appel, au risque de l'oublier ou de la recalculer inutilement ; l'encapsulation rend la faute impossible.

2.

class Chercheur:
    def __init__(self, motif):
        self.motif = motif
        self.dernier = {}
        for k in range(len(motif)):          # le pretraitement, une fois
            self.dernier[motif[k]] = k
        self.comparaisons = 0

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

    def contient(self, texte):
        return self.positions(texte) != []

    def __repr__(self):
        return f"Chercheur({self.motif!r})"

c = Chercheur("CHAT")
print(c)                            # Chercheur('CHAT')
print(c.dernier)                    # {'C': 0, 'H': 1, 'A': 2, 'T': 3}
print(c.positions("ONCHERCHECHAT")) # [9]
print(c.comparaisons)               # 7

3. Un algorithme subtil se valide contre un algorithme évident. On tire deux mille couples au hasard sur un alphabet volontairement pauvre — ce qui multiplie les répétitions et les cas limites — et on exige l'égalité des résultats.

import random
random.seed(2026)

ok = True
for _ in range(2000):
    texte = "".join(random.choice("ABC")
                    for _ in range(random.randint(0, 20)))
    motif = "".join(random.choice("ABC")
                    for _ in range(random.randint(1, 4)))
    if Chercheur(motif).positions(texte) != recherche_naive(texte, motif):
        ok = False
print("2000 tests aleatoires :", ok)   # 2000 tests aleatoires : True

4. La méthode contient est une fonction booléenne d'un argument : elle se passe directement à filter. Voilà de l'objet et du fonctionnel dans la même expression.

DOCUMENTS = ["LECHATDORT", "LECHIENAIME", "UNCHATNOIR", "RIENICI"]
print(list(filter(c.contient, DOCUMENTS)))
# ['LECHATDORT', 'UNCHATNOIR']

random.seed(1)
grand = "".join(random.choice("ACGT") for _ in range(200000))
ch = Chercheur("GATTACA")
print(len(ch.positions(grand)), ch.comparaisons)   # 9 92710

La recherche naïve, instrumentée de la même façon, effectue $266267$ comparaisons pour trouver les mêmes neuf occurrences : Boyer--Moore en fait environ $2,9$ fois moins. Le prétraitement, lui, a coûté sept tours de boucle.