Задача №113580. Маленький Матеж и большие проблемы
У маленького Матежа возникла проблема с решением следующей задачи.
У него есть множество слов, содержащее N слов. Ему пришло Q запросов, являющихся шаблонами. Шаблон состоит из строчных латинских букв и символа '*'.
Требуется узнать, сколько слов из множества могут совпасть с шаблоном, если вместо '*' подставить любое (возможно, пустое) множество букв.
В первой строке содержатся N и Q ( 1 ≤ N , Q ≤ 10 5 ). В последующих N строках содержатся строки из множества. В последующих Q строках содержатся шаблоны. Входной файл содержит не более трех миллионов символов.
Выведите Q строк: в каждой ответ для соответствующего шаблона.
40 баллов: 1 ≤ N , Q ≤ 1000
3 3 aaa abc aba a*a aaa* *aaa
2 1 1
5 3 eedecc ebdecb eaba ebcddc eb e* *dca e*c
5 0 2