Олимпиадный тренинг

Задача . E. Электронное правительство


Задача

Темы: Деревья дп поиск в глубину и подобное Строки Структуры данных *2800

В рамках проекта «Электронное правительство» лучшим программистам страны Распиляндии поручили создание системы автоматизации сбора статистики и анализа прессы.

Известно, что членами правительства Распиляндии может стать любой из k граждан. Их фамилии — a1, a2, ..., ak. Все фамилии различны. Изначально в правительство входят все k граждан из этого списка. Система должна поддерживать следующие возможности:

  • Включить гражданина ai в состав правительства.
  • Исключить гражданина ai из состава правительства.
  • По заданному тексту статьи определить, насколько она политизирована. Для этого, для каждого действующего члена правительства, вычисляется количество раз, которое его фамилия встречается в тексте как подстрока. Считаются все вхождения, в том числе и пересекающиеся. Степень политизированности текста определяется как сумма этих количеств по всем действующим членам правительства.

Реализуйте эту систему.

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

В первой строке через пробел записаны числа n и k (1 ≤ n, k ≤ 105) — количество запросов к системе и количество потенциальных членов правительства.

В следующих k строках заданы фамилии a1, a2, ..., ak, по одной на строку. Все фамилии попарно различны.

В следующих n строках заданы запросы к системе, по одному на строку. Каждый запрос состоит из символа, определяющего операцию, и аргумента операции, записанных подряд без пробела.

Операции «включить в правительство» соответствует символ «+», операции «исключить» — «-». Аргументом этих операций является целое число от 1 до k — номер гражданина, которого она затрагивает. Любой гражданин может быть включен и исключен из правительства произвольное количество раз в любом порядке. Включение в правительство гражданина, который в него уже входит, или исключение гражданина, который и так не входил, ничего не меняет.

Операции «подсчитать политизированность» соответствует символ «?». Её аргументом является текст.

Все строки, как фамилии, так и тексты, являются непустыми последовательностями строчных букв латинского алфавита. Суммарная длина всех фамилий не превышает 106, суммарная длина всех текстов не превышает 106.

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

Для каждой операции «подсчитать политизированность» выведите на отдельной строке степень политизированности заданного в ней текста. Для остальных операций ничего выводить не нужно.


Примеры
№Входные данныеВыходные данные
1 7 3
a
aa
ab
?aaab
-2
?aaab
-3
?aaab
+2
?aabbaa 
6
4
3
6

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет