Школа программиста
Резервная копия - VPS Hoster 

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Поиск в сети Меганет

(Время: 2 сек. Память: 16 Мб Сложность: 71%)

Для проведения чемпионата мира по поиску в сети Меганет организаторам необходимо ограничить доступ к некоторым адресам. Адрес в сети Меганет представляет собой строку, состоящую из имени сервера и имени раздела.

Имя сервера представляет собой строку, содержащую от одной до пяти частей включительно. Каждая часть представляет собой непустую строку, состоящую из строчных букв английского алфавита. Части разделены точкой. Примеры корректных имен сервера: «a», «ab.cd», «abacaba», «a.b.c.d.e».

Имя раздела представляет собой строку, которая может быть либо пустой, либо содержать от одной до пяти частей включительно. Каждая часть начинается с символа «/», после которого следует одна или несколько строчных английских букв. Примеры корректных имен разделов: «», «/a», «/aba», «/a/b/c/d/e».

Адрес формируется приписыванием имени раздела в конец имени сервера. Например, корректными адресами являются строки: «a», «aba/d/f/g/h», «a.b», «aba.caba/def/g», «c.d.e.f.g/a/b/c/d/e».

Для ограничения доступа к некоторым адресам сети Меганет организаторы чемпионата подготовили несколько фильтров. Фильтр, как и адрес, состоит из двух частей: фильтра сервера и фильтра раздела.

Фильтр сервера состоит из имени сервера, перед которым может также идти строка «*.». Если фильтр сервера представляет собой только имя сервера, то этому фильтру соответствует только сервер, имеющий точно такое же имя. Если фильтр сервера представляет собой строку «*.S», где S – имя сервера, то ему соответствуют сервера, удалением нуля или более начальных частей от имени которых можно получить строку S.

Аналогично, фильтр раздела представляет собой имя раздела, после которого может идти строка «/*». Фильтру раздела, который представляет собой просто имя раздела R, соответствуют только разделы, в точности совпадающие с R. Если фильтр раздела представляет собой строку «R/*», то ему соответствуют все разделы, удалением от имен которых нуля или более конечных частей можно получить строку R. Адрес соответствует фильтру, если его имя сервера соответствует фильтру сервера, а его имя раздела соответствует фильтру раздела.

Примеры фильтров и соответствующих им адресов приведены в таблице ниже.

ФильтрПримеры подходящих адресов
ab.c/d/eab.c/d/e
*.aa; ax.a; efg.a
*.a/b/ca/b/c; ax.a/b/c; efg.a/b/c
x.yz/a/*x.yz/a; x.yz/a/b/c; x.yz/a/xyz
*.a/*a; x.a; e.fg.a; a/b/c; x.a/ddd/c; e.fg.a/b/c/g/haha/i
*.a/b/c/*a/b/c; x.a/b/c; e.fg.a/b/c; a/b/c/xxx; e.fg.a/b/c/d/e/f

Требуется написать программу, которая по заданному набору фильтров и списку адресов определяет для каждого адреса, какому числу фильтров соответствует этот адрес.

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

Первая строка входного файла INPUT.TXT содержит целое число n – количество фильтров (1 ≤ n ≤ 50 000). Последующие n строк содержат фильтры, по одному на строке. Каждый фильтр удовлетворяет ограничениям, описанным выше. Следующая строка содержит одно целое число k – количество адресов, которые необходимо проверить на соответствие фильтрам (1 ≤ k ≤ 50 000). Последующие k строк содержат адреса, по одному на строке. Каждый адрес удовлетворяет ограничениям, описанным выше. Длина каждой строки входного файла не превышает 50 символов. Общий размер входного файла не превышает 4 мегабайт.

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

В выходной файл OUTPUT.TXT выведите k целых чисел, по одному на строке – для каждого адреса необходимо вывести количество фильтров, которым соответствует этот адрес.

Примеры

INPUT.TXTOUTPUT.TXT
12
a.bb/c
bb/c/d
4
a.bb
bb/c/d
a.bb/c/d
bb/c
0
1
0
0
24
*.bb/c
*.bb/c/*
bb/c/*
bb/c/*
6
bb
bb/c
bb/c/d
a.bb
a.bb/c
a.bb/c/d
0
4
3
0
2
1

Пояснения к примерам

В первом примере в фильтрах не встречается символ «*», поэтому адрес соответствует фильтру только в случае полного совпадения.

Во втором примере следует обратить внимание на то, что фильтры могут повторяться, а также, что фильтрам вида «*./…» соответствуют также адреса, в которых часть имени сервера полностью совпадает с соответствующей частью фильтра. Аналогично фильтрам «…//*» соответствуют также адреса, в которых часть имени раздела полностью совпадает с соответствующей частью фильтра.


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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 A. Выбор зала
 B. Призы
 C. Река
 D. Поиск в сети Меганет
 E. Кольцевая линия
 F. Вырубка леса
 G. Укладка плитки
 H. Магические порталы

Красноярский краевой Дворец пионеров, (c)2006 - 2022, ICQ: 151483, E-mail: admin@acmp.ru



Купить диплом о высшем образовании с 2013 по 2021 год купить диплом 2021 года.