Database basato sui prefissi
All’inizio disponi di un database vuoto e devi gestire una serie di query. Esistono due tipi di query: “Add (aggiungi)” e “Search (cerca)”. La query “Add” aggiunge un nome al database, mentre la query “Search” richiede di mostrare tutti i nomi nel database che iniziano con un determinato prefisso, in ordine lessicografico. Tuttavia, se ci sono più di 20 nomi che corrispondono al prefisso, devi restituire soltanto i primi 20.
Input (Ingresso)
Il primo rigo contiene un intero
q (1 ≤ q ≤ 200 000), che rappresenta il numero di query. Le q righe successive contengono le query, con il seguente formato:- Per le query “Add”:
add s(dovesè il nome da aggiungere al database).
- Per le query “Search”:
search p(dovepè il prefisso da cercare).
La lunghezza delle stringhe nelle query non supera i 20 caratteri.
Output (Uscita)
Per ogni query “Search”, stampa i nomi del database che iniziano con il prefisso indicato, separati da uno spazio. Se i nomi corrispondenti al prefisso sono più di 20, mostrane soltanto i primi 20.
Esempi
Esempio di Input | Esempio di 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