Pesquisa por Prefixos
É-lhe fornecido um dicionário que inicialmente não contém nenhuma palavra. É necessário processar uma série de consultas, cada uma pertencendo a um de dois tipos:
- Consulta de Tipo 1: Adicionar uma palavra ao dicionário.
- Input:
1 word(1 ≤ |word| ≤ 1000), wherewordis a non-empty string consisting of lowercase English letters. - Action: Add the word to the dictionary.
- Consulta de Tipo 2: Contar quantas palavras começam por um determinado prefixo.
- Input:
2 prefix(1 ≤ |prefix| ≤ 1000), whereprefixis a non-empty string consisting of lowercase English letters. - Output: Output the number of words in the dictionary that start with the given prefix.
- Entrada:
2 prefix (1 ≤ |prefix| ≤ 1000), onde prefix é uma cadeia de caracteres não vazia composta por letras minúsculas em inglês.Entrada
A primeira linha da entrada contém um único inteiro,
n (1 ≤ n ≤ 100 000), que representa o número de consultas.As
n linhas seguintes contêm as consultas, em um dos seguintes formatos:1 wordpara uma consulta de Tipo 1.
2 prefixpara uma consulta de Tipo 2.
Garante-se que o número total de caracteres na entrada não excede .
Saída
Para cada consulta de Tipo 2, escreva uma linha com um único inteiro que representa quantas palavras no dicionário começam pelo prefixo fornecido.
Exemplos
Entrada | Saída |
7
1 aba
1 abac
1 caba
2 ab
1 caba
1 cd
2 c | 2
3 |
Constraints
Time limit: 7 seconds
Memory limit: 512 MB
Output limit: 1 MB