Ricerca per prefisso
Ti viene fornito un dizionario che inizialmente non contiene alcuna parola. Devi gestire una serie di richieste, ciascuna appartenente a uno dei due tipi seguenti:
- Query di tipo 1: Aggiungere una parola al dizionario.
- Input:
1 word(1 ≤ |word| ≤ 1000), wherewordis a non-empty string consisting of lowercase English letters. - Action: Add the word to the dictionary.
- Query di tipo 2: Contare quante parole iniziano con un prefisso specifico.
- 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), dove prefix è una stringa non vuota di lettere minuscole dell’alfabeto inglese.Input
La prima riga di input contiene un intero
n (1 ≤ n ≤ 100 000), che rappresenta il numero di query.Le
n righe successive contengono le query, ciascuna in uno dei seguenti formati:1 wordper una query di tipo 1.
2 prefixper una query di tipo 2.
È garantito che il numero totale di caratteri nell’input non superi .
Output
Per ogni query di tipo 2, stampa un intero su una nuova riga: il numero di parole nel dizionario che iniziano con il prefisso fornito.
Esempi
Input | Output |
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