Búsqueda de Prefijos
Se te proporciona un diccionario que inicialmente no contiene ninguna palabra. Debes procesar una serie de consultas, y cada consulta pertenece a uno de los siguientes dos tipos:
- Consulta de tipo 1: Agregar una palabra al diccionario.
- 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 cuántas palabras empiezan con un determinado prefijo.
- 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.
- Input:
2 prefix (1 ≤ |prefix| ≤ 1000), donde prefix es una cadena no vacía formada por letras minúsculas en inglés.Entrada
La primera línea de la entrada contiene un único entero,
n (1 ≤ n ≤ 100 000), que representa el número de consultas.Las siguientes
n líneas contienen las consultas. Cada línea tendrá uno de los siguientes formatos:1 wordpara una consulta de tipo 1.
2 prefixpara una consulta de tipo 2.
Se garantiza que el número total de caracteres en la entrada no supera .
Salida
Para cada consulta de tipo 2, debes imprimir en una nueva línea un único número que represente la cantidad de palabras en el diccionario que comienzan con el prefijo dado.
Ejemplos
Entrada | Salida |
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