NSI (terminale) · Chapitre 16 · Application directe du cours

Table du mauvais caractère à la main

Calculabilité, décidabilité et paradigmes de programmation · niveau 2

É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$ .

Corrigé

On garde la dernière occurrence de chaque lettre :


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$ .

100 % gratuit

Essaie le suivant avec le tuteur

Faire l'exercice suivant avec le tuteur

Sans compte : le cours, 2 minutes de podcast et de vidéo et un exercice avec le tuteur. Pour tout le reste : inscription gratuite en 30 secondes, sans carte bancaire.

Le cours du chapitre · Tous les exercices du chapitre

Exercice suivant avec le tuteur →