Dictionary search#5908
Given a set of dictionary rows s_1, s_2, \ldots, s_n, and a set of query rows q_1, q_2, \ldots, q_m, for each query row q_i, determine how many of the dictionary rows have q_i as a prefix.
Formally, for each , find the number of indices such that q_i is a prefix of s_t.
The first line contains two integers and (1 \leq n, m \leq 10^5). Each of the next lines contains a non-empty dictionary row s_i. Each of the next lines contains a non-empty query row q_i. Note that rows in the set may repeat.
Output integers: the -th integer should equal the number of dictionary rows for which q_i is a prefix.
Example 1