시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 122 7 6 14.286%

문제

낙원이는 OOP(객체 지향 프로그래밍) 랩실에서 연구를 하고 있는데, 너무 바빠서 데이터를 정리할 시간이 없다. 데이터 중 정해진 패턴과 일치하는 데이터가 몇 개씩 있는지 찾아야한다. 그 방법은 다음과 같다.

N개의 단어가 들어있는 집합이 있고, Q개의 패턴이 있다. 각 패턴에는 알파벳 소문자(a~z)와 단 1개의 별표(*)가 포함되어있다.

어떤 패턴이 단어를 감싼다는 것은 패턴에 포함된 "*"을 적당한 알파벳들로 바꾸었을 때 완전히 같은 단어가 된다는 것이다. 이때, 별표 자리에 아무것도 넣지 않는 것 또한 포함된다.

시간이 없는 낙원이를 위해 데이터 정리를 도와주자.

입력

첫째 줄에 단어의 개수 N과 패턴의 개수 Q가 주어진다. (1 ≤ N, Q ≤ 100,000)

이어서 N개의 줄에 각각의 단어가 주어지며, 단어들은 모두 알파벳 소문자로만 이루어져있다.

이후 Q개의 줄에 각각의 패턴이 주어지며, 패턴들은 모두 알파벳 소문자와 별표 하나(*)로만 이루어져있다.

전체 글자 수는 3,000,000을 넘지 않는다.

출력

k번째 줄에 k번째 패턴이 감싸는 단어의 개수를 Q개의 줄에 걸쳐 출력한다.

예제 입력 1

3 3
aaa
abc
aba
a*a
aaa*
*aaa

예제 출력 1

2
1
1

예제 입력 2

5 3
eedecc
ebdecb
eaba
ebcddc
eb
e*
*dca
e*c

예제 출력 2

5
0
2
W3sicHJvYmxlbV9pZCI6IjExODc4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiT09QIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIwOTlcdWM2ZDBcdWM3NzRcdWIyOTQgT09QKFx1YWMxZFx1Y2NiNCBcdWM5YzBcdWQ1YTUgXHVkNTA0XHViODVjXHVhZGY4XHViNzk4XHViYzBkKSBcdWI3YTlcdWMyZTRcdWM1ZDBcdWMxMWMgXHVjNWYwXHVhZDZjXHViOTdjIFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YjEwOFx1YmIzNCBcdWJjMTRcdWJlNjBcdWMxMWMmbmJzcDtcdWIzNzBcdWM3NzRcdWQxMzBcdWI5N2MgXHVjODE1XHViOWFjXHVkNTYwIFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM1YzZcdWIyZTQuIFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWM5MTEgXHVjODE1XHVkNTc0XHVjOWM0IFx1ZDMyOFx1ZDEzNFx1YWNmYyBcdWM3N2NcdWNlNThcdWQ1NThcdWIyOTQgXHViMzcwXHVjNzc0XHVkMTMwXHVhYzAwIFx1YmE4NyBcdWFjMWNcdWM1MjkgXHVjNzg4XHViMjk0XHVjOWMwIFx1Y2MzZVx1YzU0NFx1YzU3Y1x1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD5OXHVhYzFjXHVjNzU4IFx1YjJlOFx1YzViNFx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjOWQxXHVkNTY5XHVjNzc0IFx1Yzc4OFx1YWNlMCwgUVx1YWMxY1x1Yzc1OCBcdWQzMjhcdWQxMzRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMzI4XHVkMTM0XHVjNWQwXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTAoYX56KVx1YzY0MCBcdWIyZTggMVx1YWMxY1x1Yzc1OCZuYnNwO1x1YmNjNFx1ZDQ1YygqKVx1YWMwMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWQzMjhcdWQxMzRcdWM3NzQgXHViMmU4XHVjNWI0XHViOTdjIFx1YWMxMFx1YzJmY1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDAgXHVkMzI4XHVkMTM0XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxYyAmcXVvdDsqJnF1b3Q7XHVjNzQ0IFx1YzgwMVx1YjJmOVx1ZDU1YyBcdWM1NGNcdWQzMGNcdWJjYjNcdWI0ZTRcdWI4NWMgXHViYzE0XHVhZmI4XHVjNWM4XHVjNzQ0IFx1YjU0YyBcdWM2NDRcdWM4MDRcdWQ3ODggXHVhYzE5XHVjNzQwIFx1YjJlOFx1YzViNFx1YWMwMCBcdWI0MWNcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YmNjNFx1ZDQ1YyBcdWM3OTBcdWI5YWNcdWM1ZDAgXHVjNTQ0XHViYjM0XHVhYzgzXHViM2M0IFx1YjEyM1x1YzljMCBcdWM1NGFcdWIyOTQgXHVhYzgzIFx1YjYxMFx1ZDU1YyBcdWQzZWNcdWQ1NjhcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM1YzZcdWIyOTQgXHViMDk5XHVjNmQwXHVjNzc0XHViOTdjIFx1YzcwNFx1ZDU3NCBcdWIzNzBcdWM3NzRcdWQxMzAgXHVjODE1XHViOWFjXHViOTdjIFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVhY2ZjIFx1ZDMyOFx1ZDEzNFx1Yzc1OCBcdWFjMWNcdWMyMTggUVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiwgUSAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzViNFx1YzExYyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjMDFcdWFjMDFcdWM3NTggXHViMmU4XHVjNWI0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHViMmU4XHVjNWI0XHViNGU0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IFFcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQzMjhcdWQxMzRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWQzMjhcdWQxMzRcdWI0ZTRcdWM3NDAgXHViYWE4XHViNDUwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWM2NDAgXHViY2M0XHVkNDVjIFx1ZDU1OFx1YjA5OCgqKVx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzhcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgwNFx1Y2NiNCBcdWFlMDBcdWM3OTAgXHVjMjE4XHViMjk0IDMsMDAwLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPmtcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIGtcdWJjODhcdWM5ZjggXHVkMzI4XHVkMTM0XHVjNzc0IFx1YWMxMFx1YzJmOFx1YjI5NCBcdWIyZThcdWM1YjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFFcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTE4NzgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJPT1AiLCJkZXNjcmlwdGlvbiI6IjxwPkxpdHRsZSBNYXRlaiBpcyBzb2x2aW5nIGFuIE9PUCAoT2JqZWN0LW9yaWVudGVkIHByb2dyYW1taW5nKSBsYWJvcmF0b3J5IGV4ZXJjaXNlIGFuZCBoZSZyc3F1bztzIGhhdmluZyB0cm91YmxlIHdpdGggc29sdmluZyBvbmUgc3VidGFzay48XC9wPlxyXG5cclxuPHA+SGUgaXMgZ2l2ZW4gYSBzZXQgdGhhdCBjb250YWlucyBOIHdvcmRzLiBIZSBpcyBhbHNvIGdpdmVuIFEgcXVlcmllcyB3aGVyZSBlYWNoIHF1ZXJ5IGlzIG9uZSBwYXR0ZXJuLiBBIHBhdHRlcm4gY29uc2lzdHMgb2YgYSBzaW5nbGUgY2hhcmFjdGVyICZsZHF1bzsqJnJkcXVvOyBhbmQgbG93ZXJjYXNlIGxldHRlcnMgb2YgdGhlIEVuZ2xpc2ggYWxwaGFiZXQuIEZvciBleGFtcGxlLCAmbGRxdW87KiZyZHF1bzssICZsZHF1bztrdWwqdG8mcmRxdW87LCAmbGRxdW87YW5hKiZyZHF1bzsuPFwvcD5cclxuXHJcbjxwPkEgcGF0dGVybiBpcyBzYWlkIHRvIGNvdmVyIGEgd29yZCBpZiBzdWNoIGFuIGFycmF5IG9mIGxldHRlcnMgKHdoaWNoIGNhbiBiZSBlbXB0eSkgZXhpc3RzIHRoYXQsIHdoZW4gcmVwbGFjaW5nIHRoZSBjaGFyYWN0ZXIgJmxzcXVvOyomcnNxdW87LCB0aGUgcGF0dGVybiBhbmQgdGhlIHdvcmQgYmVjb21lIGNvbXBsZXRlbHkgaWRlbnRpY2FsLiBJdCBpcyBuZWNlc3NhcnkgdG8gb3V0cHV0IGhvdyBtYW55IHdvcmRzIGVhY2ggcGF0dGVybiBjb3ZlcnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgUSAoMSAmbGU7IE4sIFEgJmxlOyAxMDAgMDAwKS48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgYSB3b3JkIHRoYXQgY29uc2lzdHMgb2YgbG93ZXJjYXNlIGxldHRlcnMgb2YgdGhlIEVuZ2xpc2ggYWxwaGFiZXQuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBRIGxpbmVzIGNvbnRhaW5zIGEgcGF0dGVybiBmb3Igd2hpY2ggeW91IG5lZWQgdG8gb3V0cHV0IGhvdyBtYW55IHdvcmRzIGZyb20gdGhlIGZpcnN0IHNldCBpdCBjb3ZlcnMuPFwvcD5cclxuXHJcbjxwPlRoZSB0b3RhbCBudW1iZXIgb2YgY2hhcmFjdGVycyB3aWxsIGJlIGxlc3MgdGhhbiAzIDAwMCAwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IFEgbGluZXMsIHRoZSBrPHN1cD50aDxcL3N1cD4gbGluZSBjb250YWluaW5nIHRoZSBudW1iZXIgb2Ygd29yZHMgdGhhdCB0aGUgazxzdXA+dGg8XC9zdXA+IHBhdHRlcm4gY292ZXJzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2015/2016 > Contest #5 5번