P6727 [COCI 2015/2016 #5] OOP

Given $N$ words and $Q$ patterns, each pattern consists of one `*` and some lowercase letters. A pattern matches a word if and only if, after replacing `*` with some string (**which can be empty**), the pattern and the word can coincide exactly. For each pattern, find how many words it can match.

The first line contains two integers $N, Q$. The next $N$ lines each contain a word consisting of lowercase letters. The next $Q$ lines each contain a pattern. The total number of characters read is less than $3\times 10^6$.

Output $Q$ lines. Each line contains the number of words that the corresponding pattern can match.

#### Constraints For $40\%$ of the testdata, $1\le N, Q\le 10^3$. For $100\%$ of the testdata, $1\le N, Q\le 10^5$. #### Notes **This problem is translated from [COCI2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #5](https://hsin.hr/coci/archive/2015_2016/contest5_tasks.pdf) *T5 OOP***。 Translated by ChatGPT 5