You are given a list of n labels. Define the prefix score of a label w as follows: for each non-empty prefix p of w, count how many labels in the whole list (including w itself, and counting duplicates) have p as a prefix, and add up those counts over all prefixes of w.
Output the prefix score of each label, in the input order. All labels consist of lowercase English letters only.
Line 1: an integer n.
Line 2: n space-separated labels.
A single line with n space-separated integers: the prefix score of each label, in input order.
Example 1
Input
2 ab abc
Expected
4 5
Explanation
For ab: prefixes a (2 labels) and ab (2 labels) -> 4. For abc: prefixes a (2), ab (2), abc (1) -> 5.
Example 2
Input
2 a a
Expected
2 2
Explanation
Each a has the single prefix a, which 2 labels share, so each score is 2.
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 →