Recherche de préfixe
Vous disposez d’un dictionnaire qui est initialement vide. Vous devez traiter une série de requêtes, chacune appartenant à l’un des deux types suivants :
- Requête de type 1 : Ajouter un mot au dictionnaire.
- Input:
1 word(1 ≤ |word| ≤ 1000), wherewordis a non-empty string consisting of lowercase English letters. - Action: Add the word to the dictionary.
- Requête de type 2 : Compter le nombre de mots commençant par un préfixe donné.
- 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.
- Entrée :
2 prefix (1 ≤ |prefix| ≤ 1000), où prefix est une chaîne non vide composée de lettres minuscules anglaises.Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ 100 000), correspondant au nombre de requêtes.Les
n lignes suivantes décrivent les requêtes. Chaque ligne est dans l’un des formats suivants :1 wordpour une requête de type 1.
2 prefixpour une requête de type 2.
Il est garanti que le nombre total de caractères dans l’entrée ne dépasse pas .
Sortie
Pour chaque requête de type 2, vous devez afficher sur une nouvelle ligne le nombre de mots du dictionnaire qui commencent par le préfixe donné.
Exemples
Entrée | Sortie |
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