Algoritmos e Estruturas de Dados

Base de Dados Baseada em Prefixos

Você começa com uma base de dados vazia e precisa processar uma série de consultas. Existem dois tipos de consultas: “Add” e “Search”. A consulta “Add” adiciona um nome à base de dados, enquanto a consulta “Search” pede que sejam exibidos todos os nomes na base de dados que comecem com um determinado prefixo, em ordem lexicográfica. No entanto, se houver mais de 20 nomes que correspondam ao prefixo, exiba apenas os primeiros 20.

Entrada

A entrada começa com um inteiro q (1 ≤ q ≤ 200 000) na primeira linha, indicando o número de consultas. As próximas q linhas contêm as consultas nos seguintes formatos:
  • Para consultas “Add”: add s (onde s é o nome a ser adicionado na base de dados).
  • Para consultas “Search”: search p (onde p é o prefixo que se deseja procurar).
O comprimento das cadeias de caracteres nas consultas não ultrapassa 20 caracteres.

Saída

Para cada consulta “Search”, imprima os nomes da base de dados que começam com o prefixo fornecido, separados por um espaço. Caso existam mais de 20 nomes correspondentes ao prefixo, mostre apenas os primeiros 20.

Exemplos

Entrada
Saída
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