String Algorithms (KMP, Z, Rolling Hash, Trie)
You are given n words (repeats allowed) and q query strings. For each query, print how many of the n words start with it. A word counts once for every time it appears in the list.
The first line has n and q. The second line has the n words separated by spaces. The third line has the q queries separated by spaces.
Print q lines: the answer to each query, in order.
1 <= n, q <= 100000 The total length of all words is at most 1000000, and so is the total length of all queries. Words and queries are non-empty strings of lowercase letters.
1000 ms256 MB
5 4 apple app apt bat bath ap app ba z
3 2 2 0
Three words start with ap, two with app, two with ba, none with z.
