Различные префиксы
(Время: 5 сек. Память: 128 Мб Сложность: 42%)
Вася придумал задачу, в которой требовалось реализовать три операции:
- добавить строку s в словарь (словарь может содержать одинаковые строки);
- удалить строку s из словаря (гарантируется, что такая строка уже была ранее добавлена);
- определить количество различных префиксов длины k.
Петя, прочитав условие, сказал, что это «баян» и многие олимпиадники знают, как решить данную задачу. Попробуйте и Вы решить её (ну или вспомнить решение).
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число N – количество операций (2 ≤ N ≤ 105).
В следующих N строках описаны сами операции. В начале каждой строки содержится целое число type (1 ≤ type ≤ 3), обозначающее тип операции. Если тип операции равен 1 или 2, то далее дана строка s (|s| ≤ 105) состоящая из строчных английских букв, которую нужно добавить или удалить соответственно. Если тип равен 3, то далее следует одно целое число 1 ≤ k ≤ 105 - длина префикса.
Гарантируется, что суммарная длина всех строк в запросах не превышает 106.
Выходные данные
В выходной файл OUTPUT.TXT для каждой операции 3 типа выведите в отдельной строке количество различных префиксов длины k.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 10
1 abracadabra
1 aba
3 2
3 3
1 bcad
3 2
3 3
2 aba
3 2
3 3 | 1
2
2
3
2
2 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
