P10470 Prefix Statistics

Given $N$ strings $S_1,S_2,\cdots,S_N$, you will then make $M$ queries. In each query, a string $T$ is given. Find how many strings among $S_1 \sim S_N$ are prefixes of $T$. The total length of all input strings does not exceed $10^6$, and they contain only lowercase letters.

The first line contains two integers $N,M$. The next $N$ lines each contain a string $S_i$. The next $M$ lines each contain a string $T$ for querying.

For each query, output an integer representing the answer. Each answer occupies one line.

Constraints: $1 \le N,M \le 10^5$. Translated by ChatGPT 5