Exercices corrigés de NSI : recherche textuelle et algorithme de Boyer-Moore

a) $n = 9$ et $m = 3$. La variable $i$ parcourt range(n - m + 1), soit les valeurs $0$ à $6$ : $9 - 3 + 1 = 7$ fenêtres. La dernière fenêtre commence en $i = 6$ et se termine en $6 + 3 - 1 = 8$, dernier indice du texte. Une fenêtre qui commencerait en $i = 7$ réclamerait texte[9], qui n'existe pas. La borne $n - m + 1$ n'est donc pas un détail : c'est elle qui garantit que chaque fenêtre tient entière dans le texte. Écrire range(len(texte)) est l'erreur la plus fréquente sur ce code, et elle se paie par une IndexError sur les dernières positions.

b) Les fenêtres qui coïncident commencent en $1$ (a, l, a aux indices $1$, $2$, $3$) et en $3$ (a, l, a aux indices $3$, $4$, $5$) : la fonction renvoie [1, 3]. Les deux occurrences se CHEVAUCHENT, elles partagent le a d'indice $3$. La méthode count compte les occurrences sans chevauchement : après avoir trouvé ala en $1$, elle reprend la lecture en $4$ et ne voit plus rien. Notre fonction examine chaque fenêtre indépendamment des autres, donc elle trouve les deux. Les deux réponses ne répondent pas à la même question ; en génomique, c'est presque toujours la version avec chevauchement que l'on veut, et c'est celle que demandent les sujets.

c) On compte jusqu'au premier échec INCLUS : $i = 0$, b contre a, $1$ comparaison ; $i = 1$, trois égalités, $3$ ; $i = 2$, l contre a, $1$ ; $i = 3$, trois égalités, $3$ ; $i = 4$, l contre a, $1$ ; $i = 5$, a égal à a puis i contre l, $2$ ; $i = 6$, i contre a, $1$. Total : $1 + 3 + 1 + 3 + 1 + 2 + 1 = 12$ comparaisons. Une fenêtre qui coïncide coûte $m$ comparaisons, une fenêtre qui échoue coûte le rang de l'échec. Le piège de comptage est d'oublier la comparaison qui échoue : elle a bien été faite, c'est même elle qui arrête la boucle.

d) L'opérateur and évalue de gauche à droite et s'arrête dès que le premier test est faux : c'est l'évaluation paresseuse. Dans l'ordre correct, quand $k$ atteint len(motif), le test k < len(motif) est faux et l'accès motif[k] n'est jamais tenté. Dans l'ordre inversé, après trois égalités sur la fenêtre $i = 1$, $k$ vaut $3$ et Python évalue d'abord texte[4] == motif[3] : motif[3] n'existe pas, et le programme s'arrête sur une IndexError. L'erreur ne se produit qu'à la première fenêtre qui coïncide entièrement : un test sur un texte qui ne contient pas le motif ne la détecte pas. Le garde-fou se place TOUJOURS avant l'accès qu'il protège.

e) $n = 50$ et $m = 4$ : $50 - 4 + 1 = 47$ fenêtres, et toutes coïncident, donc $47$ occurrences, chacune au prix de $4$ comparaisons : $47 \times 4 = 188$. C'est le pire cas possible : aucune fenêtre ne coûte plus de $m$ comparaisons et il y a $n - m + 1$ fenêtres, donc la recherche naïve fait au plus $m(n - m + 1)$ comparaisons, de l'ordre de $n \times m$ quand le motif est court devant le texte. Pour un motif de $20$ caractères dans un texte d'un million, cela peut dépasser vingt millions de comparaisons. Tout l'enjeu de Boyer-Moore est de ne plus examiner chaque fenêtre.

a) Le motif a $m = 7$ lettres, d'indices $0$ à $6$. La boucle parcourt $k = 0$ à $5$ et écrit d[motif[k]] = 6 - k : $k = 0$, c reçoit $6$ ; $k = 1$, a reçoit $5$ ; $k = 2$, s reçoit $4$ ; $k = 3$, c est ÉCRASÉ par $3$ ; $k = 4$, a est écrasé par $2$ ; $k = 5$, d reçoit $1$. Table finale : c $3$, a $2$, s $4$, d $1$. Comme la boucle va de gauche à droite et qu'une affectation dans un dictionnaire remplace l'ancienne valeur, c'est la DERNIÈRE apparition qui gagne. C'est voulu : le décalage doit amener sous la lettre lue la copie de cette lettre la plus proche de la fin du motif, c'est-à-dire le plus PETIT déplacement possible. Un déplacement plus grand risque de sauter par-dessus une occurrence, et la question d) le montre.

b) La lettre e n'apparaît qu'en dernière position, que la boucle n'atteint jamais : elle n'est pas une clé, et d.get('e', 7) renvoie $7$. Même chose pour z, absente du motif : $7$. Le dictionnaire a $4$ clés, c, a, s et d. Le piège classique est de donner $0$ à e parce qu'elle est à distance $0$ de la fin. Or si une fenêtre se termine par un e du texte et échoue plus à gauche, aucune AUTRE copie de e ne peut venir se placer sous ce e : le motif peut passer entièrement au-delà, d'où le décalage $m$.

c) La borne range(m - 1) exclut l'indice $m - 1$, la dernière lettre. Avec range(m), la dernière itération écrirait d['e'] = 0. Dans la recherche, une fenêtre terminée par un e du texte ferait alors avancer $i$ de $0$ : la boucle while tournerait indéfiniment sur la même fenêtre. La terminaison de l'algorithme repose sur ce détail, tout décalage vaut au moins $1$. C'est une question classique de l'écrit, et la réponse attendue tient en une phrase : « on exclut la dernière lettre pour qu'aucun décalage ne soit nul ».

d) De droite à gauche, $k$ prend les valeurs $5, 4, 3, 2, 1, 0$ et la dernière écriture est celle de la PREMIÈRE apparition : c reçoit $6$ à $k = 0$, a reçoit $5$ à $k = 1$. Dans 'la cascade', $n = 10$, $n - m = 3$ et l'occurrence est en $3$. La fenêtre $i = 0$ se termine sur l'indice $6$, qui porte un c. Avec la bonne table, c donne $3$ : $i$ passe à $3$ et la fenêtre coïncide. Avec la table de l'élève, c donne $6$ : $i$ passe à $6$, qui dépasse $n - m = 3$, et la recherche s'arrête avec $0$ occurrence. Un décalage trop GRAND n'est pas une optimisation, c'est une occurrence manquée, et le programme ne signale rien.

e) La boucle fait $m - 1 = 6$ tours, une affectation par tour : $6$ affectations, quel que soit le texte. Le prétraitement ne dépend que du motif ; il se fait UNE fois, avant la lecture du texte, et son coût est négligeable dès que le texte est long. C'est l'intérêt que le programme demande de mettre en avant : un petit travail sur le motif, fait une seule fois, permet ensuite des sauts à chaque fenêtre. Si l'on cherche le même motif dans dix textes, on calcule la table une fois et on la réutilise ; la recalculer dans la boucle de recherche ne fausserait pas le résultat mais gâcherait exactement ce que le prétraitement fait gagner.

a) $m = 4$, et la boucle ne regarde que r, o, s, d'indices $0$, $1$, $2$ : r reçoit $4 - 1 - 0 = 3$, o reçoit $2$, s reçoit $1$. La dernière lettre, e, n'apparaît nulle part ailleurs : elle n'est pas une clé et donne $4$, comme l'espace, le p ou le u. Écrire la table AVANT de toucher au texte n'est pas une formalité : toute la trace ne fait plus ensuite que la consulter.

b) Fenêtre $i = 0$ : elle couvre les indices $0$ à $3$, et la lettre alignée avec la fin du motif est texte[3], un espace. On compare l'espace au e du motif : échec, $1$ comparaison. L'espace n'est pas une clé, on avance de $4$. Fenêtre $i = 4$ : indices $4$ à $7$, la lettre lue est texte[7] = s, différente de e : $1$ comparaison, et d[s] = 1, donc $i = 5$. Remarquez que le décalage se lit sur la lettre du TEXTE, s, et non sur la lettre du motif qui lui fait face : c'est l'erreur qui fausse le plus de traces.

c) $i = 5$ : texte[5..8] = rose, quatre égalités de droite à gauche, $4$ comparaisons, occurrence ; la lettre lue est e, décalage $4$, $i = 9$. $i = 9$ : lettre lue texte[12] = r, $1$ comparaison, d[r] = 3, $i = 12$ : le r du motif vient se placer exactement sous ce r. $i = 12$ : la lettre lue texte[15] est un e, qui coïncide avec la fin du motif ; on continue vers la gauche et texte[14] = l diffère de s : $2$ comparaisons, fausse alerte. Le décalage se lit toujours sur texte[15] = e, qui n'est pas une clé : $4$, $i = 16$. $i = 16$ : lettre lue o, $1$ comparaison, d[o] = 2, $i = 18$. $i = 18$ : rose, $4$ comparaisons, occurrence ; lettre e, $i = 22$, qui dépasse $n - m = 19$ : arrêt. Fenêtres : $0, 4, 5, 9, 12, 16, 18$, soit $7$.

d) Positions $5$ et $18$. Comparaisons : $1 + 1 + 4 + 1 + 2 + 1 + 4 = 14$. Contrôle rapide : deux occurrences coûtent au moins $2 \times 4 = 8$ comparaisons, et chacune des cinq autres fenêtres au moins $1$, donc $13$ au minimum ; la fausse alerte en ajoute une.

e) La recherche naïve examine les $23 - 4 + 1 = 20$ fenêtres et fait $27$ comparaisons : elle en coûte presque le double, et elle examine presque trois fois plus de fenêtres. Horspool n'a lu que les indices $3, 5, 6, 7, 8, 12, 14, 15, 18, 19, 20, 21$ (le $7$ et le $19$ deux fois) : $12$ caractères distincts, donc $23 - 12 = 11$ caractères jamais lus. C'est le trait qui distingue Boyer-Moore : il ne se contente pas de comparer moins, il SAUTE des parties du texte sans les lire. Le programme ne demande pas d'étude générale de ce coût ; il demande de savoir le constater sur un exemple, comme ici.

a) On compare de droite à gauche : le premier caractère examiné est la dernière case du motif, d'indice $m - 1$, d'où k = m - 1. Avec k = 0, on comparerait de gauche à droite et la boucle k = k - 1 sortirait aussitôt du motif ; avec k = m, le premier accès motif[m] lèverait une IndexError.

b) (2) est k >= 0 and texte[i + k] == motif[k] : on descend tant qu'il reste des cases à comparer ET que la case coïncide. Le test sur k vient en premier, pour que Python ne lise jamais texte[i + k] avec k = -1 : l'indice -1 désigne en Python le DERNIER caractère, donc l'ordre inverse ne lèverait aucune erreur, il ferait simplement une comparaison de trop hors de la fenêtre après chaque occurrence, silencieusement. Avec k > 0, la boucle s'arrête à k = 0 sans jamais comparer motif[0], et k ne vaut jamais -1 : le test (3) n'est jamais vrai et la fonction renvoie une liste vide, quel que soit le texte.

c) Si les $m$ cases ont coïncidé, la boucle a fait descendre k de m - 1 jusqu'à -1 : c'est le signe qu'aucun échec n'a eu lieu, d'où k == -1. Le test k == 0 serait vrai quand l'échec a lieu sur la première lettre, ce qui est tout le contraire d'une occurrence.

d) (4) est d.get(texte[i + m - 1], m) : la lettre lue est celle du TEXTE sous la dernière case du motif, et une lettre qui n'est pas une clé donne $m$. Les deux distracteurs sont les deux erreurs de copie les plus répandues : motif[m - 1] donne toujours la même lettre, donc toujours le même saut, et texte[i + k] mélange la table de Horspool avec la lettre de l'échec, ce qui peut faire manquer une occurrence. Terminaison : la table ne contient que des valeurs $m - 1 - k$ avec $k \le m - 2$, donc au moins $1$, et la valeur par défaut $m$ vaut au moins $1$. Chaque tour augmente $i$ d'au moins $1$, et $i$ ne peut pas dépasser $n - m$ indéfiniment : la boucle fait au plus $n - m + 1$ tours.

e) Table de 'tic' : t $2$, i $1$, et c n'est pas une clé. $i = 0$ : tic coïncide, $3$ comparaisons, lettre lue c, saut $3$. $i = 3$ : lettre lue texte[5] = a, $1$ comparaison, saut $3$. $i = 6$ : lettre lue texte[8] = t, $1$ comparaison, d[t] = 2, $i = 8$. $i = 8$ : tic coïncide, saut $3$, $i = 11 > 8$ : arrêt. Résultat [0, 8] en $4$ fenêtres et $8$ comparaisons. Avec d[texte[i + m - 1]], la première fenêtre se termine par c, qui n'est pas une clé : Python lève une KeyError dès $i = 0$. Ce n'est pas un hasard : la lettre lue à la fin d'une occurrence est toujours la dernière lettre du motif, exclue de la table sauf si elle apparaît plus tôt. Sans get, le programme plante donc à la première occurrence de presque tous les motifs.

def cherche_horspool(texte, motif):
    n, m = len(texte), len(motif)
    d = table_decalages(motif)
    res = []
    i = 0
    while i <= n - m:
        k = m - 1
        while k >= 0 and texte[i + k] == motif[k]:
            k = k - 1
        if k == -1:
            res.append(i)
        i = i + d.get(texte[i + m - 1], m)
    return res

a) Cette fois la boucle parcourt TOUT le motif, dernière lettre comprise, et range l'indice de la dernière apparition : t apparaît en $0$ puis en $4$, donc $4$ ; o $1$, m $2$, a $3$, e $5$. Ce n'est pas la table de Horspool : celle-ci range une distance à la fin et exclut la dernière case, celle-ci range une position et inclut tout. Les confondre est la première source d'erreur quand un sujet présente les deux.

b) pilote contre tomate, de droite à gauche : e et e coïncident ($k = 5$), t et t coïncident ($k = 4$), puis o contre a échoue en $k = 3$. $3$ comparaisons. La lettre de l'échec est o, dernière position $1$ dans le motif : décalage $3 - 1 = 2$. Après ce décalage, le o du motif, d'indice $1$, se trouve sous le o du texte qui a provoqué l'échec : c'est le plus petit déplacement qui ne remet pas une lettre différente en face de ce o.

c) comete contre tomate : e, puis t coïncident, puis e contre a échoue en $k = 3$. La lettre de l'échec est e, dont la dernière position dans le motif est $5$, À DROITE de l'échec : $k - 5 = -2$. Un décalage négatif ferait reculer le motif et reviendrait sur une fenêtre déjà examinée, et un décalage nul ferait tourner l'algorithme sur place. Le max(1, ...) impose d'avancer d'au moins une case : décalage $1$. C'est le cas que la règle du mauvais caractère gère mal, et c'est pour lui que Boyer-Moore complet ajoute une seconde règle, celle du bon suffixe, dont on prend le plus grand décalage ; le programme ne demande pas de la connaître.

d) violon : la première comparaison, n contre e, échoue en $k = 5$, et n n'est pas dans le motif : pos.get('n', -1) vaut $-1$ et le décalage est $5 - (-1) = 6$, le motif passe entièrement au-delà du n. Horspool, lui, lit toujours la lettre sous la fin du motif. En (1) et (2) c'est un e, dernière lettre de tomate et absente du reste du motif : décalage $6$. En (3) c'est n : $6$. Sur les fenêtres (1) et (2), Horspool saute donc de $6$ quand la règle du mauvais caractère n'avance que de $2$ et de $1$.

e) Si l'échec a lieu en $k = m - 1$ sur la lettre c, alors c est différente de la dernière lettre du motif, donc sa dernière position $j$ dans le motif entier est aussi sa dernière position parmi les $m - 1$ premières cases. Le mauvais caractère donne $m - 1 - j$, exactement la valeur de la table de Horspool ; et si c est absente, $m - 1 - (-1) = m$, comme d.get(c, m). Les deux règles ne diffèrent donc qu'après au moins une égalité. Aucune ne domine : sur pilote, Horspool saute de $6$ contre $2$. Mais avec le motif 'coucou', dont la dernière lettre u apparaît aussi en $2$, une fenêtre qui se termine par z puis u fait l'inverse : Horspool lit u et n'avance que de $6 - 1 - 2 = 3$, quand le mauvais caractère, lisant z en $k = 4$, avance de $4 - (-1) = 5$.

a) $n = 100$, $m = 5$ : $100 - 5 + 1 = 96$ fenêtres. De gauche à droite, les quatre 0 du motif coïncident avec des 0 du texte et seul le 1 final échoue : $5$ comparaisons par fenêtre, soit $96 \times 5 = 480$. C'est le pire cas de la recherche naïve : chaque fenêtre ressemble au motif sur toute sa longueur sauf la dernière case, et l'algorithme ne le découvre qu'en dernier.

b) Table de '00001' : les quatre premières cases sont des 0, la dernière apparition est en $3$, donc 0 donne $5 - 1 - 3 = 1$ ; le 1 n'est qu'en dernière case et n'est pas une clé. À chaque fenêtre, Horspool compare D'ABORD la dernière case : un 0 du texte contre le 1 du motif, échec immédiat, $1$ comparaison. La lettre lue est un 0, décalage $1$. Horspool examine donc les $96$ mêmes fenêtres que la recherche naïve, mais pour $96$ comparaisons au lieu de $480$. Ici le gain ne vient pas des sauts, qui valent $1$ : il vient du SENS de lecture, qui tombe tout de suite sur la case qui diffère.

c) Motif '10000'. Recherche naïve : le 1 initial contre un 0 échoue d'emblée, $1$ comparaison par fenêtre, $96$ au total. Horspool : table 1 donne $4$, 0 donne $1$ (dernière apparition hors fin en $3$). De droite à gauche, les quatre 0 coïncident et seul le 1 échoue : $5$ comparaisons, puis la lettre lue, un 0, donne un saut de $1$. Total $96 \times 5 = 480$. Les rôles se sont exactement inversés par rapport à a) et b) : chaque algorithme est rapide quand la case qui diffère est la première qu'il lit, et lent quand c'est la dernière. Sur ce motif, Horspool fait cinq fois plus de comparaisons que la méthode naïve.

d) Motif '11111' : la table ne contient que 1, avec le décalage $1$. Chaque fenêtre se termine par un 0, absent du motif : $1$ comparaison et un saut de $5$. Les fenêtres commencent en $0, 5, 10, \ldots, 95$, soit $20$ fenêtres et $20$ comparaisons, quand la recherche naïve en ferait $96$. Voilà le cas favorable : la lettre lue n'est pas dans le motif, et le motif passe d'un bloc au-delà d'elle. On n'a lu qu'un caractère sur cinq.

e) Non. Sur le motif '10000', Horspool fait $480$ comparaisons contre $96$ : aucune affirmation du type « Boyer-Moore est toujours plus rapide » ne résiste à ce contre-exemple, et un correcteur l'attend. Ce qui est vrai : dans les textes usuels, où la lettre lue en fin de fenêtre est souvent absente du motif ou n'y figure que loin de la fin, les sauts sont grands et Horspool examine une petite fraction des fenêtres. Les cas défavorables demandent un texte très répétitif et un motif qui lui ressemble presque partout ; ils sont rares dans un roman, beaucoup moins dans un fichier binaire ou dans une séquence d'ADN.

a) Les trois premières cases sont e, l, l : e donne $4 - 1 - 0 = 3$, l donne $3 - 1 = 2$ puis est ÉCRASÉ par $3 - 2 = 1$. Table : e $3$, l $1$. Trace : $i = 0$, lettre lue texte[3], un espace, saut $4$ ; $i = 4$, lettre l, saut $1$ ; $i = 5$, occurrence, lettre e, saut $3$ ; $i = 8$, lettre i, saut $4$ ; $i = 12$, lettre l, saut $1$ ; $i = 13$, occurrence, $i = 16 > 13$ : arrêt. $6$ fenêtres.

b) Positions $5$ et $13$. Comparaisons : $1 + 1 + 4 + 1 + 1 + 4 = 12$. Les deux sauts de $1$ sont ceux qui sauvent les deux occurrences : à chaque fois la fenêtre se terminait sur un l, et le dernier l du motif, placé juste avant la fin, est venu se mettre dessous.

c) Variante A : fenêtres $0, 4, 8, 12$, puis $16 > 13$. Aucune ne coïncide : $0$ occurrence, pour $4$ comparaisons. La fenêtre $i = 4$ se terminait sur un l ; en sautant de $4$, on passe de 'bell' à 'e fi' sans jamais essayer $i = 5$, qui était une occurrence. Un saut fixe de $m$ ne serait juste que si la lettre lue n'apparaissait nulle part dans le motif. L'élève a gagné du temps et perdu toutes les réponses : un sujet qui demande « l'algorithme est-il correct ? » attend précisément ce contre-exemple, avec le texte et la position manquée.

d) Variante B : $i = 0$, saut $4$ ; $i = 4$, lettre l, saut $2$ au lieu de $1$, donc $i = 6$ : l'occurrence en $5$ est sautée. $i = 6$, lettre lue un espace, saut $4$ ; $i = 10$, lettre e, qui coïncide, puis c contre l échoue, saut $3$ ; $i = 13$, occurrence ; $i = 16$ : arrêt. Une seule occurrence, en $13$, et encore par chance. La première apparition donne un décalage trop grand dès qu'une lettre est répétée : c'est la raison pour laquelle la boucle du prétraitement va de gauche à droite et laisse la dernière écriture gagner.

e) Supposons qu'il y ait une occurrence en $i + t$ avec $0 < t < s$. Le motif posé en $i + t$ place sa case d'indice $m - 1 - t$ sous la position $i + m - 1$ du texte, qui porte la lettre c ; une occurrence exige donc motif[m - 1 - t] = c. Or $m - 1 - t$ est compris entre $m - s$ et $m - 2$ : c'est une case, hors dernière, située STRICTEMENT à droite de l'indice $m - 1 - s$, qui est la dernière apparition de c parmi les $m - 1$ premières cases (ou $-1$ si c n'y est pas, quand $s = m$). Contradiction. Le décalage de la table est donc le plus grand saut sûr, et tout saut plus grand, comme en c) et d), peut manquer une occurrence.

a) Le motif part du début du texte, en $i = 0$, et glisse vers la droite : les positions testées sont croissantes, et les occurrences sont renvoyées dans l'ordre croissant. Ce qui va de droite à gauche, c'est la comparaison À L'INTÉRIEUR d'une fenêtre : k part de m - 1 et descend. Énoncé correct : « Boyer-Moore fait glisser le motif de gauche à droite et, dans chaque fenêtre, compare les caractères de droite à gauche. » La confusion fait écrire des traces qui commencent par la fin du texte : toute la question est perdue.

b) La table est calculée par table_decalages(motif), qui ne reçoit même pas le texte en paramètre : elle ne peut pas en dépendre. Elle est construite UNE fois, avant la boucle de recherche. Ce qui change à chaque fenêtre, c'est la CLÉ avec laquelle on la consulte, la lettre texte[i + m - 1]. Énoncé correct : « le prétraitement ne dépend que du motif ; on le fait une fois, puis chaque fenêtre ne coûte qu'une consultation du dictionnaire. » C'est exactement l'intérêt du prétraitement que le programme demande de mettre en avant.

c) Sur un secteur de $100$ zéros, le motif '10000' coûte $480$ comparaisons à Horspool et $96$ à la recherche naïve : de droite à gauche, les quatre 0 coïncident avant que le 1 échoue, alors que la recherche naïve bute sur le 1 dès la première case. Énoncé correct : « Horspool fait souvent beaucoup moins de comparaisons, surtout quand les lettres lues sont absentes du motif, mais il existe des textes où il en fait plus que la recherche naïve. » Un seul contre-exemple suffit à réfuter un « toujours ».

d) La fonction doit renvoyer la liste de TOUTES les positions. Après une occurrence, on enregistre $i$ puis on avance du décalage de la lettre lue, exactement comme après un échec, et l'on continue jusqu'à $i > n - m$. S'arrêter à la première occurrence est une autre fonction, utile parfois (« le motif est-il présent ? »), mais ce n'est pas celle qu'on demande. Attention aussi à ne pas sauter de $m$ après une occurrence : deux occurrences peuvent se chevaucher, comme ala dans balalaika.

e) Si aucun caractère du texte n'est dans le motif, chaque fenêtre coûte $1$ comparaison et fait sauter de $m$ : les fenêtres commencent en $0, m, 2m, \ldots$ Pour $m = 4$ : $\frac{12\,000}{4} = 3\,000$ fenêtres ; pour $m = 12$ : $\frac{12\,000}{12} = 1\,000$ fenêtres, trois fois moins. Énoncé correct : « avec Boyer-Moore, un motif plus long permet des sauts plus longs ; dans les cas favorables, la recherche est d'autant plus rapide que le motif est long. » C'est le contraire exact de l'intuition, et du comportement de la recherche naïve, dont le pire cas croît avec $m$.

a) Parmi les cinq premières cases G, A, A, T, T : G donne $6 - 1 - 0 = 5$, A donne d'abord $4$ puis, à sa dernière apparition en $2$, $3$ ; T donne $2$ puis, en $4$, $1$. Table : G $5$, A $3$, T $1$. La lettre C n'apparaît qu'en dernière case, exclue de la table : elle donne $m = 6$. Une fenêtre qui se termine par un C, qu'elle coïncide ou non, fait donc sauter le motif tout entier.

b) $i = 0$ : lettre lue T (indice $5$) contre C, $1$ comparaison, saut $1$. $i = 1$ : la fenêtre TGAATC se termine par C, qui coïncide ; puis T contre T coïncide ; puis A contre T échoue : $3$ comparaisons. Cette fenêtre contient GAATC, un site auquel il manque un T : ce n'est pas un site EcoRI, et l'algorithme le rejette en trois comparaisons. Lettre lue C, saut $6$, $i = 7$. $i = 7$ : T, $1$ comparaison, saut $1$. $i = 8$ : GAATTC, $6$ comparaisons, site trouvé, saut $6$. $i = 14$ : T, saut $1$. $i = 15$ : T, saut $1$. $i = 16$ : site, $6$ comparaisons, saut $6$, $i = 22 > 18$ : arrêt. $7$ fenêtres.

c) Sites en $8$ et $16$. Comparaisons : $1 + 3 + 1 + 6 + 1 + 1 + 6 = 19$. La recherche naïve, sur ses $19$ fenêtres, en fait $34$ : l'économie est de $34 - 19 = 15$ comparaisons, soit $\frac{15}{34} \approx 44\ \%$. C'est un gain réel mais modeste, et la question suivante dit pourquoi.

d) Les décalages possibles sont $5$ pour G, $3$ pour A, $1$ pour T et $6$ pour C. Si les quatre lettres sont également fréquentes en fin de fenêtre, le saut moyen vaut $\frac{5 + 3 + 1 + 6}{4} = 3{,}75$, loin du maximum $6$. Sur un alphabet de quatre lettres, toutes les lettres ou presque figurent dans le motif, et la lettre lue fait rarement sauter tout le motif. Dans un texte en français, avec une trentaine de caractères et un motif d'une dizaine de lettres distinctes, la lettre lue est le plus souvent absente du motif, et le saut vaut $m$. C'est pourquoi, en bio-informatique, on préfère des variantes qui lisent plusieurs lettres à la fois pour décider du saut ; l'idée du prétraitement reste la même.

e) Le premier site commence en $8$ : la coupure passe entre l'indice $8$ (le G) et l'indice $9$. Premier fragment : indices $0$ à $8$, $9$ bases. Le second site commence en $16$ : coupure entre $16$ et $17$. Deuxième fragment : indices $9$ à $16$, $8$ bases. Troisième : indices $17$ à $23$, $7$ bases. Contrôle : $9 + 8 + 7 = 24$, la longueur du fragment. Chaque site est coupé juste APRÈS sa position, puisque la coupure suit le G initial : confondre la position d'un site avec celle de la coupure décale tous les fragments d'une base.

a) $m = 7$ et les six premières lettres f, r, o, m, a, g sont toutes distinctes : f $6$, r $5$, o $4$, m $3$, a $2$, g $1$, soit $6$ clés. La lettre e n'est qu'en dernière case : elle n'est pas une clé et donne $7$. Un motif dont les lettres sont toutes distinctes a la table la plus simple qui soit, chaque lettre y recevant sa distance à la fin.

b) La fenêtre $i = 42$ se termine en $48$, sur le o de son : d[o] = 4, donc $i = 46$, ce qui place le o du motif (indice $2$) sous ce o. La fenêtre $i = 53$ se termine en $59$, sur le r de fromage : d[r] = 5, donc $i = 58$, et le r du motif vient sous ce r ; la fenêtre $58$ coïncide. La fenêtre $i = 28$ se termine en $34$, sur le é de perché. Pour Python, é et e sont deux caractères DIFFÉRENTS : é n'est pas une clé, la comparaison é contre e échoue, et le saut vaut $7$. C'est ici sans conséquence, mais c'est la même raison qui fera échouer la question e).

c) La recherche naïve examine les $66 - 7 + 1 = 60$ fenêtres. Dans chacune, elle compare d'abord la première lettre au f du motif ; le seul f du vers est celui de fromage, en $58$. Les $59$ autres fenêtres coûtent donc $1$ comparaison chacune, et la fenêtre $58$ en coûte $7$ : $59 + 7 = 66$ comparaisons, contre $18$ pour Horspool, qui n'a examiné que $10$ fenêtres. Sur un texte en langue naturelle, où la lettre lue en fin de fenêtre est rarement dans le motif, Horspool saute presque toujours de $m$.

d) $66 - 17 = 49$ caractères n'ont jamais été lus, près des trois quarts du vers. C'est ce qu'on appelle un comportement sous-linéaire dans les cas favorables : l'algorithme conclut sans même regarder la plus grande partie du texte, ce qu'aucune méthode qui lit caractère par caractère ne peut faire. Le programme n'exige pas de démontrer ce coût, mais il faut savoir le constater sur une trace comme celle-ci.

e) La fonction renvoie une liste vide, $0$ occurrence : le vers écrit Renard avec un R majuscule, et 'R' est différent de 'r'. L'algorithme n'est pas en cause, il compare des caractères, pas des mots. La correction se fait AVANT la recherche : on cherche le motif en minuscules dans vers.lower(), qui donne 'maître renard, ...' et fait apparaître l'occurrence en $7$. Les accents posent le même problème : chercher 'alleche' ne trouve pas alléché. Une bibliothèque numérique normalise donc le texte, minuscules et souvent accents retirés, une seule fois, exactement comme on prétraite le motif une seule fois.