950. Adding Up Every Prefix Score
You are given n words. The SCORE of a word is computed like this: take each
non-empty prefix of it in turn, count how many of the n words begin with that
prefix, and add those counts up.
Print the n scores, in input order, on one line separated by single spaces.
abc ab bc b cc -> 5 4 3 2 2
abcd abcd -> 8 8
ab abc abcd -> 6 8 9
xyz -> 3
Check the first score by hand. The prefixes of abc are a, ab and abc.
Two words begin with a (abc and ab), two begin with ab (the same two),
and one begins with abc. That is 2 + 2 + 1 = 5.
And the second row: both words are abcd, so each of the four prefixes is shared
by both, giving 2 + 2 + 2 + 2 = 8 for each of them.
## What the direct program costs
For each word, for each of its prefixes, scan all n words. That is
n * 20 * n prefix comparisons, which at n = 20000 is 8 * 10^9, each costing
up to 20 character comparisons of its own.
## The trie already holds every one of those counts
Insert all n words, incrementing a counter at every node each word passes
through. Then cnt[v] is the number of words beginning with the prefix v
stands for, which is precisely the quantity being summed.
So the score of a word is the sum of the counters along its own path.
build the trie, cnt[node] += 1 at every step of every insertion
for each word w:
node = root, score = 0
for each letter c of w:
node = child[node][c]
score += cnt[node]
print score
Two passes over the input, and no comparison between words anywhere.
## Why walking the word gives exactly the right terms
The nodes on a word's path from the root, excluding the root itself, are in one
to one correspondence with its non-empty prefixes: the node at depth k is the
prefix of length k, and no prefix is missed or repeated. So the sum along the
path is the sum over prefixes, term for term.
The root is excluded because the empty prefix is not a prefix the question asks
about; including it would add n to every score.
## Repeats need no special handling
A word that appears twice increments every counter on its path twice, which is
right: both copies do begin with each of those prefixes. That is why abcd abcd
gives 8 and not 4, and why nothing in the method deduplicates.
## Overflow
Nothing here overflows. A word has at most 20 prefixes and each counter is at
most n = 20000, so a score is at most 20 * 20000 = 400000, which is comfortably
inside a signed 32 bit integer. The sum of all the scores could reach 20000 *
400000 = 8 * 10^9 and would need 64 bits, but that total is not asked for.
## Cost
Time O(total characters) to build and the same to score. Space is the trie,
at most 400001 nodes.
Constraints - `1 ≤ n ≤ 20000` - Every word is 1 to 20 lowercase English letters. - Words may repeat.
Input
The first line contains an integer n.
The next n lines each contain one word.
Output
Print n integers on a single line, separated by single spaces, in the input order of the words: the prefix score of each word. Print no other text.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.