informatique (MP2I/MPI) · Chapitre 18 · Application directe du cours
La table du mauvais caractère
Algorithmique des textes · niveau 2
Énoncé
Construire la table derniere pour les motifs exemple, texte et abcab. Pour chacun, dire de combien on saute si l'échec a lieu à la dernière position du motif sur la lettre z, puis sur la lettre e.
Corrigé
La table donne, pour chaque lettre, sa dernière position dans le motif (indices à partir de ), ou si elle n'y figure pas.
exemple : e->6 l->5 m->3 p->4 x->1 (toute autre lettre -> -1)
texte : e->4 t->3 x->2 (toute autre lettre -> -1)
abcab : a->3 b->4 c->2 (toute autre lettre -> -1)Noter que derniere retient la dernière occurrence, et pas la première : dans abcab, la lettre a apparaît en et en , on garde .
Les sauts, pour un échec en :
| Motif | échec sur z | échec sur e | |
|---|---|---|---|
exemple | 7 | ||
texte | 5 | ||
abcab | 5 |
Sur une lettre absente du motif, le saut vaut tout entier : c'est le gain que le chapitre annonce, et c'est la raison pour laquelle Boyer-Moore lit moins de caractères qu'il n'y en a.
Sur la lettre e avec le motif exemple, en revanche, le saut calculé vaut — l'échec porte sur une lettre qui est déjà, dans le motif, à la position où l'on a échoué. La garde le remonte à . Ce cas n'est pas exotique : il se produit dès que la lettre fautive est la dernière du motif, ce qui arrive tout le temps sur un alphabet réduit.
