Competitive Programming Wing

0

0 votes
Trie, Medium, Strings
Problem

IIIT Codeland is organising a contest in order to select the members for its competitive programming wing. Buddy is taking part in the contest since he aspires to be the next co-ordinator of the wing. He is stuck in a question in the contest and decides to cheat. He sends you the problem statement. You are given N words and Q queries. In each query, you'll be provided with a string Qi. Determine how many unique words have the queried string as a proper prefix. A proper prefix of a string S is a substring S which occurs at the beginning of a S, but is not the entire string S. Help Buddy get into the programming wing :) 


INPUT FORMAT

First line of each test file would contain 2 integers - N, the number of strings and Q - the number of query strings.

The following N lines contain a string Si. Any string may be repeated any number of times.

The following Q lines contain a string Qi - representing the query string as described in the problem.


OUTPUT FORMAT

For each query, output the required answer in a new line.


CONSTRAINTS  

     1   N ,  Q  105  

     1   length(Qi), length(Si)100

Time Limit: 2
Memory Limit: 100
Source Limit:
Explanation

The UNIQUE strings having abc as a proper prefix are: abcd, abce - 2 strings

Similarly for ab we have: abc, abcd, abce, abe - 4 strings

Editor Image

?