A warehouse keeps a list of n shelf labels (a label may appear more than once; repeats are counted separately). You are then given q prefix queries. For each query prefix, report how many labels in the list have that prefix (a label counts if the query string is a prefix of it; a label is a prefix of itself).
All labels and prefixes consist of lowercase English letters only.
Line 1: an integer n.
Line 2: n space-separated labels.
Line 3: an integer q.
Line 4: q space-separated query prefixes.
Print q lines; line i is the number of labels having the i-th query as a prefix.
Example 1
Input
3 apple app apply 3 app appl ban
Expected
3 2 0
Explanation
apple, app, apply all start with app -> 3. Only apple and apply start with appl -> 2. No label starts with ban -> 0.
Example 2
Input
1 cat 2 ca xyz
Expected
1 0
Explanation
cat starts with ca -> 1. Nothing starts with xyz -> 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →