TrieString
Given a list of words and a prefix, count how many of the words start with that prefix. Try to answer using a trie (prefix tree), the data structure that makes prefix questions fast.
Input
Line 1: n, the number of words. Line 2: the n words. Line 3: the prefix. All are lowercase letters.
Output
Print the number of words that start with the prefix.
Constraints
1 <= n <= 10^4 1 <= length of each word, prefix <= 20
Example 1
Input
5 apple app apply ape bat ap
Output
4
apple, app, apply and ape start with ap.