Algorithmes et Structures de Données

Base de données basée sur les préfixes

Au départ, on vous fournit une base de données vide et vous devez traiter une série de requêtes. Il existe deux types de requêtes : "Add" et "Search". La requête "Add" ajoute un nom dans la base de données, tandis que la requête "Search" vous demande d’afficher tous les noms de la base de données qui commencent par un préfixe donné, dans l’ordre lexicographique. Toutefois, si plus de 20 noms correspondent à ce préfixe, vous ne devez afficher que les 20 premiers.

Entrée

L’entrée commence par un entier q (1 ≤ q ≤ 200 000) sur la première ligne, qui représente le nombre de requêtes. Les q lignes suivantes contiennent les requêtes au format suivant :
  • Pour les requêtes "Add" : add s (où s est le nom à ajouter à la base de données).
  • Pour les requêtes "Search" : search p (où p est le préfixe à rechercher).
La longueur des chaînes de caractères dans les requêtes ne dépasse pas 20 caractères.

Sortie

Pour chaque requête "Search", affichez les noms de la base de données qui commencent par le préfixe indiqué, séparés par un espace. S’il y a plus de 20 noms qui correspondent au préfixe, n’affichez que les 20 premiers.

Exemples

Input
Output
9 add cat add code add core search co add profound add found search fo add fight search f
code core found fight found
 

Constraints

Time limit: 6 seconds

Memory limit: 512 MB

Output limit: 15 MB

To check your solution you need to sign in
Sign in to continue