A1314 | [COCI-2015_2016-contest5]#2 OOP

Little Matej is solving an OOP (Object-oriented programming) laboratory exercise and he’s having trouble with solving one subtask.
He is given a set that contains N words. He is also given Q queries where each query is one pattern. A pattern consists of a single character “*” and lowercase letters of the English alphabet. For example, “*”, “kul*to”, “ana*”.
A pattern is said to cover a word if such an array of letters (which can be empty) exists that, when replacing the character ‘*’, the pattern and the word become completely identical. It is necessary to output how many words each pattern covers.
I

The first line of input contains two integers N and Q (1 6 N, Q 6 100 000).
Each of the following N lines contains a word that consists of lowercase letters of the English alphabet.
Each of the following Q lines contains a pattern for which you need to output how many words from the first set it covers.
The total number of characters will be less than 3 000 00
0.

Output Q lines, the k th line containing the number of words that the k th pattern covers.