Sum of Prefix Scores of Strings

For each word, compute the sum of counts of how many words in the array share each of its non-empty prefixes. The core challenge is efficiently computing prefix frequencies across all words (commonly via a trie or prefix-hashmap) to handle up to ~10^6 total characters.