Requêtes de suffixe commun le plus long
(Bataille de rap)
On vous donne une liste de
n mots distincts : , ainsi qu’une liste de q mots de requête . Votre objectif est de trouver, pour chaque mot w, le mot de la liste a qui est à la fois différent de w et qui partage avec lui le suffixe commun le plus long, puis de renvoyer celui qui est le plus petit dans l’ordre lexicographique.Entrée
La première ligne de l’entrée contient un seul entier,
n (2 ≤ n ≤ 25 000), qui représente le nombre de chaînes dans la liste.Les
n lignes suivantes contiennent les chaînes. Chaque chaîne est composée de lettres anglaises minuscules et sa longueur ne dépasse pas 30 caractères.La ligne suivante contient un seul entier,
q (1 ≤ q ≤ 25000), qui indique le nombre de chaînes de requête.Les
q lignes suivantes contiennent les chaînes de requête.Chaque chaîne est composée de lettres anglaises minuscules et sa longueur ne dépasse pas 30 caractères.
Sortie
Pour chaque requête, vous devez afficher sur une ligne distincte le mot le plus petit dans l’ordre lexicographique parmi ceux de la liste, différent du mot de requête, et qui partage avec ce mot le plus long suffixe en commun.
Exemples
Entrée | Sortie |
4
perfect
rhyme
crime
time
2
crime
rhyme | time
crime |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB