Table du mauvais caractère à la main

Application directe du cours · niveau 2 · NSI (terminale), chapitre 16 — Calculabilité, décidabilité et paradigmes de programmation

Énoncé

Table du mauvais caractère à la main.

Donner la table du mauvais caractère du motif BANANE, puis celle du motif ANANAS.
Le motif BANANE est aligné sur un texte et la comparaison échoue à l'indice $j = 5$ face au caractère B du texte. De combien décale-t-on ?
Même question avec le caractère S, puis avec le caractère A et un échec à l'indice $j = 2$ .


print(table_mauvais_caractere("BANANE"))
# {'B': 0, 'A': 3, 'N': 4, 'E': 5}
print(table_mauvais_caractere("ANANAS"))
# {'A': 4, 'N': 3, 'S': 5}

Dans BANANE, le A apparaît en $1$ et en $3$ : on retient $3$ . Le N apparaît en $2$ et en $4$ : on retient $4$ .

B est en position $k = 0$ , d'où un décalage $max (1, 5 - 0) = 5$ : on aligne le B du motif sur celui du texte.
S est absent : $k = - 1$ et le décalage vaut $max (1, 5 + 1) = 6$ , la longueur entière du motif — le saut maximal. Pour A avec $j = 2$ : $k = 3 > j$ , l'aligner ferait reculer le motif, donc le décalage vaut $max (1, 2 - 3) = 1$ .

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.