Алгоритмы и структуры данных

Поиск по префиксу

Вам дан словарь, который изначально не содержит ни одного слова. Необходимо обработать последовательность запросов, каждый из которых относится к одному из двух типов:
  1. Запрос типа 1: Добавить слово в словарь.
      • Input: 1 word (1 ≤ |word| ≤ 1000), where word is a non-empty string consisting of lowercase English letters.
      • Action: Add the word to the dictionary.
  1. Запрос типа 2: Посчитать количество слов, начинающихся с заданного префикса.
      • Input: 2 prefix (1 ≤ |prefix| ≤ 1000), where prefix is a non-empty string consisting of lowercase English letters.
      • Output: Output the number of words in the dictionary that start with the given prefix.
- Формат ввода: 2 prefix (1 ≤ |prefix| ≤ 1000), где prefix — непустая строка из строчных букв английского алфавита.

Входные данные

Первая строка содержит целое число n (1 ≤ n ≤ 100000), обозначающее количество запросов.
В следующих n строках даны сами запросы. Каждая строка имеет один из следующих форматов:
  • 1 word для запроса типа 1.
  • 2 prefix для запроса типа 2.
Гарантируется, что общее количество символов во входных данных не превышает .

Выходные данные

Для каждого запроса типа 2 выведите в отдельной строке одно целое число — количество слов в словаре, начинающихся с данным префиксом.

Пример

Вход
Выход
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

To check your solution you need to sign in
Sign in to continue