Invocation – Épreuve régionale 2023

Niveau 4

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

Contraintes d'exécution

Utilisation mémoire maximum
400000 kilo-octets
Temps d'exécution maximum
200 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
2
abracada
abra
3
abra
cad
c
Exemple de sortie
1
3
Commentaire

Les 3 syllabes sont abra, cad et c. Voici les prédictions possibles :

  • abracada : abra-cad-abra
  • abra : abra-abra-abra abra-cad-abra abra-c-abra
Exemple d'entrée
3
o
poustou
oustou
3
oust
ou
flan
Exemple de sortie
6
0
2
Commentaire

Voici les prédictions possibles :

  • o : ou-flan-ou ou-ou-ou oust-flan-oust ou-oust-ou oust-oust-oust oust-ou-oust
  • poustou :
  • oustou : oust-oust-oust oust-ou-oust
Exemple d'entrée
8
o
trol
admin
proloogin
trollo
trolo
trololo
mypasswordis123
9
admin
login
ogin
olorp
porlo
prolo
tro
troll
trolo
Exemple de sortie
18
19
9
1
2
10
1
0