Präfixsuche
Sie haben ein Wörterbuch, das anfangs keine Einträge enthält. Nun sollen Sie eine Reihe von Abfragen bearbeiten, die in eine von zwei Kategorien fallen:
- Abfragetyp 1: Ein Wort zum Wörterbuch hinzufügen.
- Input:
1 word(1 ≤ |word| ≤ 1000), wherewordis a non-empty string consisting of lowercase English letters. - Action: Add the word to the dictionary.
- Abfragetyp 2: Zählen, wie viele Wörter mit einem bestimmten Präfix beginnen.
- 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.
- Eingabe:
2 prefix (1 ≤ |prefix| ≤ 1000), wobei prefix ein nichtleerer String aus Kleinbuchstaben (Englisch) ist.Eingabe
In der ersten Zeile der Eingabe steht eine ganze Zahl
n (1 ≤ n ≤ 100 000), die die Anzahl der Abfragen angibt.In den folgenden
n Zeilen befinden sich die Abfragen, jeweils entweder:1 wordfür eine Abfrage vom Typ 1.
2 prefixfür eine Abfrage vom Typ 2.
Es ist sichergestellt, dass die Gesamtzahl der Zeichen in der Eingabe nicht überschreitet.
Ausgabe
Für jede Abfrage vom Typ 2 geben Sie in einer neuen Zeile eine ganze Zahl aus, die die Anzahl der Wörter im Wörterbuch angibt, die mit dem eingegebenen Präfix beginnen.
Beispiele
Eingabe | Ausgabe |
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