Texte abimé – Épreuve régionale 2024

Niveau 2 ⋅ Validation weight: 100%

Énoncé

Jøsëf et ses acolytes cherchent un moyen d'entrer au Valhalla. Au cours de leurs recherches, ils se retrouvent alors devant d'anciennes fresques semblant décrire un moyen d'y entrer. Le seul soucis : les mots sont un peu… effacés.

Ils ont noté les phrases qui se trouvaient sur les fresques, en essayant de déchiffrer comme ils pouvaient le texte manquant. Malheureusement, leur texte fait très peu de sens.

Jøsëf sait que les phrases qu'il cherche commencent par un motif de longueur $M$. Il va donc analyser le texte en considérant les points suivants :

  • Jøsëf doit analyser les $M$ premiers caractères de chaque phrase.
  • Si le i-ème caractère de la phrase ne correspond pas au i-ème caractère du motif (avec $0 \le i < M$), on considère cela comme une erreur. Une phrase est candidate uniquement si son nombre d'erreurs est inférieur ou égal à un seuil donné.

Parmi les phrases données, filtrez uniquement les phrases candidates, et affichez-les par nombre d'erreurs croissant. En cas d'égalité sur le nombre d'erreurs, l'ordre n'a pas d'importance.

Entrée

L’entrée contiendra :

  • Sur la première ligne, une chaine de 32 caractères ou moins : motif, le motif à retrouver.
  • Sur la ligne suivante, un entier : seuil, le nombre maximum d'erreurs autorisées pour qu'une phrase soit candidate.
  • Sur la ligne suivante, un entier : N, le nombre de phrases à traiter.
  • Sur les lignes suivantes, une liste de N éléments : phrases, les phrases à traiter.
    • Une ligne par élément de la liste : une chaine de 64 caractères ou moins.

Sortie

Affichez, sur une ligne par phrase et par ordre croissant du nombre d'erreurs, la liste des phrases candidates. Si aucune phrase candidate n'existe, affichez Aucune phrase valide.

Contraintes

  • $0 \le \text{seuil} \le 32$
  • $1 \le N \le 50$
  • Les phrases sont toujours plus longues que le motif

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
valhalla
1
6
la tour de valhalla est un lieu de repos pour les guerriers
volhalla est si houte quan peut a peine en uoir le zommet
ualhalla ezt un emdroit de chaix pour trovver des fonces armees
valhalia comtient six cenl quaronte porfes
ualkalla ezt sovz la pnotectian d obin
valhalla se trouue au sein b'asgard
Exemple de sortie
valhalla se trouue au sein b'asgard
ualhalla ezt un emdroit de chaix pour trovver des fonces armees
valhalia comtient six cenl quaronte porfes
volhalla est si houte quan peut a peine en uoir le zommet
Commentaire

Ici, les phrases valides sont ceux ayant au plus une erreur (seuil = 1).

La première phrase n'est pas valide, car le début ne correspond pas du tout au motif indiqué.

Les 3 suivantes ne contiennent qu'une seule erreur, elles sont donc considérées comme candidates.

En revanche, celle qui suit contient 2 erreurs, ce qui est au dessus du seuil autorisé.

La dernière correspond exactement au motif, elle est donc valide aussi.

Voici alors la liste des phrases valides, triées par nombre d'erreurs :

  • (0 erreur) : valhalla se trouue au sein b'asgard
  • (1 erreur) : ualhalla ezt un emdroit de chaix pour trovver des fonces armees
  • (1 erreur) : valhalia comtient six cenl quaronte porfes
  • (1 erreur) : volhalla est si houte quan peut a peine en uoir le zommet

Les trois dernières phrases ayant le même nombre d'erreurs, on peut les afficher dans l'ordre voulu.

Exemple d'entrée
le ragnarok
3
5
apocalyyse le ragnaror annnnce la fin du moode
l eclaa du creeuscule markue le debut ineluqtaale du raggarok
les sarpemts geantt s affromttnt dans leeragnnrok
la prophitee vikigg pradit un catoclisme le kagnarok
au ragnorak le casmos trample les cyeux s efoondrrnt
Exemple de sortie
Aucune phrase valide
Commentaire

Parmi les cinq phrases données, la phrase contenant le moins d'erreurs est :

  • au ragnorak le casmos trample les cyeux s efoondrrnt

Le préfixe au ragnorak contient quatre erreurs comparé au motif attendu, le ragnarok.

Toutes les phrases contiennent donc plus que 3 erreurs, qui est le nombre seuil d'erreur attendu. Il n'y a donc aucune phrase candidate. On affiche alors : Aucune phrase candidate.