Le saut qui recule

Il suffit que la lettre fautive figure dans le motif après la position de l'échec. Le plus petit exemple : $P=\text{ba}$ et $T=\text{aaaaa}$.

La table vaut $\mathtt{derniere}[\text{b}]=0$ et $\mathtt{derniere}[\text{a}]=1$. Trace, sans la garde :

tour 1 : i=0   echec en j=0 sur 'a', saut = 0 - 1 = -1,   i <-- -1
tour 2 : i=-1  echec en j=0 sur ' ', saut = 0 - (-1) = 1, i <-- 0
tour 3 : i=0   echec en j=0 sur 'a', saut = 0 - 1 = -1,   i <-- -1
tour 4 : i=-1  ...  (le cycle se repete indefiniment)

Deux fautes, pas une. La boucle ne termine pas — c'est celle que le chapitre annonce. Mais avant cela, le tour $2$ lit t[-1] : un accès hors tableau, exactement la faute du chapitre chap:langage-c, que C ne signale pas. Le programme peut donc, selon ce qui se trouve avant le texte en mémoire, boucler, s'arrêter au hasard, ou planter.

La preuve de terminaison. Le variant est $n-i$. Il est entier, minoré par $0$ dans la boucle (dont la condition est $i+m\le n$), et il décroît strictement à chaque tour si et seulement si $i$ augmente d'au moins $1$. La garde saut > 1 ? saut : 1 est précisément ce qui garantit cette croissance stricte. Sans elle, il n'y a pas de variant, et l'algorithme n'a pas de raison de terminer — ce que la trace confirme.

À retenir. Une expression qui a l'air d'une précaution (« au cas où ») mérite qu'on cherche le cas. Ici, le cas existe, il est atteint sur un texte de cinq lettres, et il fait deux dégâts. Quand une garde protège une terminaison, on l'écrit en commentaire à côté du variant, pas comme une prudence anonyme.