A story of name – Épreuve régionale 2022

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

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
5
maurice
marcel
clara
corinne
eric
Exemple de sortie
ma
Exemple d'entrée
5
abc
abc
aacd
aacd
acc
Exemple de sortie
aacd