시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 70 4 3 12.000%

문제

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

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

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

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

입력

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

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

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

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

출력

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

예제 입력

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

예제 출력

2
1
1

예제 입력 2

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

예제 출력 2

5
0
2

힌트

출처

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