Invocation – Épreuve régionale 2023

Énoncé¶

Le présent du mathématicien tout juste récupéré, les jeunes commencent à essayer de comprendre son utilité.

Nos amis se séparent en deux groupes, le premier cherche à comprendre l'utilité de la récompense du mathématicien et le deuxième part en exploration. En revenant, le deuxième groupe se retrouve nez-à-nez avec une sorcière. Tout le monde sait que les sorcières existaient au Moyen Âge. La sorcière les menace de les faire disparaître via un sortilège. Heureusement, vous avez précédemment lu «Comment casser un sortilège pour les noobs — Spécial sorcières».

Les sorcières connaissent un ensemble de syllabes, leur vocabulaire.

Le temps de réagir, la sorcière va commencer à épeler son sortilège. Si vous parvenez à deviner combien de sorts peuvent être épelés à partir du début de sa phrase, vous cassez son invocation.

Un sortilège est toujours composé de trois syllabes de son vocabulaire. La première et dernière syllabe doivent être la même.

En d'autres mots, un sortilège est sous forme $A + B + A$ avec $A$ et $B$ deux syllabes du vocabulaire.

Si abra et cad font partie du vocabulaire, alors abracadabra est un sortilège valide car il peut être découpé en 3 syllabes abra-cad-abra.

Pour chaque début de sortilège, indiquez combien de sorts lui correspondent, c'est-à-dire combien de sorts possèdent le début indiqué comme préfixe.

Attention : Le début du sortilège n'est pas forcément une syllabe, il peut contenir une portion de syllabe ou bien plusieurs syllabes, voire même le sortilège entier.

Entrée¶

L’entrée contiendra :

• Sur la première ligne, un entier : n, le nombre de débuts de sortilèges.
• Sur les lignes suivantes, une liste de n éléments : mots, la liste des débuts de sortilèges.
  • Une ligne par élément de la liste : une chaîne de k caractères ou moins.
• Sur la ligne suivante, un entier : m, la taille du vocabulaire.
• Sur les lignes suivantes, une liste de m éléments : vocabulaire, le vocabulaire sous forme de liste de chaînes de caractères.
  • Une ligne par élément de la liste : une chaîne de k caractères ou moins.

Sortie¶

Afficher n lignes, la i-ème ligne doit contenir le nombre de sortilèges correspondants au i-ème début de sortilège.

Contraintes¶

Les syllabes du vocabulaire et les débuts de sortilèges ne contiennent que des lettres non accentuées [a-zA-Z].

Le vocabulaire ne contient que des mots uniques mais les débuts de sortilèges ne sont pas forcément différents.

• $k = 20$, $k$ désigne la taille maximale d'un sortilège
• $1 \le n \le 10$
• $1 \le m \le 50$

Contraintes de performance¶

• $k = 60$
• $1 \le n \le 10^4$
• $1 \le m \le 100$