Le pire cas du naïf, compté exactement

Le motif ne peut jamais être trouvé : le texte n'a pas de b. À chaque alignement $i$, les $m-1$ premières comparaisons réussissent (a contre a) et la $m$-ième échoue. Chaque alignement coûte donc exactement $m$ comparaisons, et il y a $n-m+1$ alignements :

$$C(n,m)=(n-m+1)m.$$

Mesure (compteur incrémenté à chaque test t[i+j] == p[j]), avec $m=4$ :

n= 8  comparaisons = 20   (n-m+1)*m = 20
n= 9  comparaisons = 24   (n-m+1)*m = 24
n=10  comparaisons = 28   (n-m+1)*m = 28
n=11  comparaisons = 32   (n-m+1)*m = 32
n=12  comparaisons = 36   (n-m+1)*m = 36

Le maximum de $m\mapsto (n-m+1)m$ est atteint en $m=(n+1)/2$ et vaut environ $n^2/4$ : le pire cas absolu est un motif de longueur la moitié du texte, et il coûte $n^2/4$ comparaisons.

Ce que le pire cas ne dit pas. Sur du français, le premier caractère comparé suffit à conclure dans plus de neuf alignements sur dix — mesuré à $97,7\%$ pour le motif motif et $91,4\%$ pour texte, sur le texte du banc d'essai, plus bas. Le coût moyen est alors $\Theta (n)$, avec environ $1+1/(|\Sigma |-1)$ comparaison par alignement, soit $1,04$ sur vingt-six lettres équiprobables. Le pire cas de cet exercice demande un texte presque périodique : il se rencontre sur de l'adn, sur du binaire, sur des images — pas sur du texte. C'est pourquoi le chapitre écrit que la méthode naïve « survit dans bien des programmes » : la borne du pire cas ne suffit pas à condamner un algorithme, il faut savoir si son pire cas est celui de l'usage.