938. Autocomplete Suggestions
You are given n words and then q prefixes. For each prefix, print the
first three words in alphabetical order that begin with it, space separated on
one line. If fewer than three match, print all of them. If none match, print
none.
This is what a search box does, and it is the query a hash set cannot serve: it would have to examine every word it holds. Walking to the prefix node costs the length of the prefix, and the matches are everything in the subtree below it.
Visiting children in alphabetical order gives alphabetical results for free, so no sorting is needed at query time.
Constraints - `1 ≤ n ≤ 5000` - `1 ≤ q ≤ 5000` - Every word and prefix is 1 to 20 lowercase English letters. - The words are distinct.
Input
The first line contains an integer n.
The next n lines each contain one word.
The next line contains an integer q.
The next q lines each contain one prefix.
Output
For each prefix print one line: up to three matching words in alphabetical order separated by single spaces, or none if nothing matches.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.