Chaîne la plus longue atteignable
On vous fournit un ensemble de chaînes de caractères. Votre objectif est de repérer la chaîne la plus longue que l’on peut construire en ajoutant des caractères sur la gauche, en partant initialement d’une chaîne vide, tout en veillant à ce que chacune des chaînes intermédiaires apparaisse dans l’ensemble de départ. S’il existe plusieurs chaînes de longueur maximale, il faut retourner celle dont l’ordre lexicographique est le plus petit.
Entrée
La première ligne contient un entier
n (1 ≤ n ≤ 100 000), qui représente le nombre de chaînes incluses dans l’ensemble initial.
Les n lignes suivantes comportent chacune l’une des chaînes de l’ensemble. Chaque chaîne est formée de lettres minuscules de l’alphabet anglais et a une longueur comprise entre 1 et 30.Sortie
Affichez la chaîne la plus longue qui peut être construite à partir de l’ensemble donné. Si aucune chaîne ne satisfait les conditions, affichez une chaîne vide.
Exemples
Entrée | Sortie |
7
pr
profound
f
found
fo
foun
fou | found |
3
ab
abc
abcd | ㅤ |
5
a
ab
aba
abaz
abad | abad |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB