Count Strings with Given Prefixes

Problem Given N prefixes and M strings (M > N), count for each prefix how many of the strings start with it.

Input / Output

• Input: a list of N prefix strings and a list of M candidate strings
• Output: for each prefix, the count of strings having it as a prefix

Constraints

• All strings lowercase a-z; M > N
• Total input length large enough that the O(N*M) pairwise comparison is too slow
• A string is a prefix of itself — an exact match counts

Example

• prefixes = ["ab", "c"], strings = ["abc", "abd", "cat", "dog"] → ab: 2, c: 1
• Tricky case: prefix "abc" against strings ["abc", "abcd"] → 2, since the exact match counts too; and a prefix absent from the trie must return 0 rather than error