Dérouler Boyer--Moore

Dérouler Boyer--Moore. On cherche le motif RAT dans le texte LE CHAT ET LE RAT ($17$ caractères, espaces compris, numérotés de $0$ à $16$), avec la règle du mauvais caractère : quand la comparaison, faite de droite à gauche, échoue à l'indice $j$ du motif sur le caractère c du texte, on décale le motif de $\max (1,j-k)$, où $k$ est l'indice de la dernière occurrence de c dans le motif ($-1$ s'il est absent).

• Donner la table du mauvais caractère de RAT.
• Dérouler l'algorithme : pour chaque alignement $i$ essayé, donner les caractères comparés, l'indice d'échec et le décalage.
• Combien de comparaisons de caractères Boyer--Moore effectue-t-il ? Combien la recherche naïve en effectue-t-elle ?
• À l'alignement $i=4$, l'échec a lieu sur un caractère absent du motif, et pourtant on ne décale que de $1$. Pourquoi ?