Bubble Cup X - Finals [Online Mirror] |
---|
Закончено |
Смит проснулся в углу грязной, давно не использовавшейся ванной комнаты. Его щиколотки пристегнуты цепями к трубам. Рядом с ним лежит кассетный проигрыватель, на нем надпись от руки: «Послушай меня». Он находит кассету в его заднем кармане. После того, как он вставил кассету в проигрыватель, он видит ключ, свисающий с потолка, прицепленный к некой машине, которая подключена к терминалу рядом с ним. После того, как он нажал «Play», зазвучал грубый голос:
«Слушай, Смит. Как ты можешь видеть, ты в достаточно тяжелой ситуации, чтобы спастись, тебе надо отгадать загадку.
Тебе даны N строк, которые описывают слова. Каждое слово имеет максимальную длину L и состоит из символов от «a» до «e». Тебе также даны M строк, которые описывают шаблоны.
Шаблон — это строка длины ≤ L, состоящая из символов от «a» до «e», а так же не более 3 символов «?». Символ «?» — неизвестный символ, что значит, что он может быть равен любому из символов от «a» до «e», а также пустому символу.
Для каждого шаблона найди число слов, которые соответствуют данному шаблону. После того, как ты решишь задачу и введешь ответы в терминал, ключ упадет с потолка и ты сможешь убежать. Да начнется игра.»
Помогите Смиту спастись.
Первая строка содержит два целых числа N и M (1 ≤ N ≤ 100 000, 1 ≤ M ≤ 5000) — число слов и число шаблонов, соответственно.
Следующие N строк содержат слова, после этих N строк, следуют M строк, описывающих шаблоны. Каждое слово и каждый шаблон имеют максимальную длину L (1 ≤ L ≤ 50). В каждом шаблоне есть не более трех символов «?». Каждый шаблон содержит не более трех символов «?». Все другие символы в словах и шаблонах являются строчными латинскими буквами от «a» до «e».
Выведите M строк, в каждой — одно число, описывающее число слов, которые соответствуют очередному шаблону.
3 1
abc
aec
ac
a?c
3
Если мы изменим '?' на 'b', 'e' и пустой символ, мы получим 'abc', 'aec' и 'ac', соответственно.
Название |
---|