A story of name – Regional event 2022

Level 2

Énoncé

Vos grands amis Monsieur et Madame Passûr viennent d'avoir un enfant et doivent remplir une déclaration de naissance. Le problème étant qu'ils n'ont pas encore réussi à se décider sur un prénom, et que le temps presse car ils sont à la mairie devant le papier !

Ils doivent à tout prix commencer à écrire quelque chose, et afin de gagner quelques précieuses secondes pour se décider, ils tentent de trouver la suite de lettres qui leur laissera le plus de choix de prénom.

Ils se tournent vers vous, l'air désemparés. C'est avec joie que vous lancez votre meilleur algorithme sur le coup. Comme leur donner une seule lettre ne va pas les aider, vous considérez qu'un préfixe est composé d'au moins 2 lettres.

Trouvez le plus long préfixe d'au moins deux lettres commun à un maximum de prénoms.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : taille, la taille de la liste de prénoms.
  • Sur les lignes suivantes, une liste de taille éléments : noms, la liste de mots dont on doit extraire le préfixe.
    • Une ligne par élément de la liste : une chaine pouvant contenir jusqu'à 255 caractères.

Sortie

Afficher le préfixe commun au plus de mots de la liste passée en entrée.

Si plusieurs préfixes sont communs au même nombre de mots, on affichera le plus long d'entre eux, et en cas d'égalité, le premier dans l'ordre lexicographique.

Contraintes

  • $2 \le taille \le 20\,000$

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
5
maurice
marcel
clara
corinne
eric
Sample output
ma
Sample input
5
abc
abc
aacd
aacd
acc
Sample output
aacd

Submit your solution

You have to register or log in to be able to submit your solution.