Loading...
Loading...
Loading...
A catalogue stores n product codes. For each of q prefixes, print how many stored codes start with it. A code starts with itself, and a code stored twice counts twice.
Example 1
Input
5 4 car cart cat dog car ca car d z
Output
4 3 1 0
ca matches 4 codes, counting car twice.
Example 2
Input
1 1 ab abc
Output
0
Try the problem first. Open one hint at a time.
Store in each trie node how many words pass through it.
The answer for a prefix is the count at its node, or 0 if the walk fails.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor