A routing table stores n dictionary entries. For each of q query strings, find the longest dictionary entry that is a prefix of the query (an entry w matches a query x if x starts with w). Because the matching entries of a given query all have distinct lengths, the longest match is unique.
If no dictionary entry is a prefix of the query, print NONE. All strings consist of lowercase English letters only. Duplicate dictionary entries are allowed and behave like a set.
Line 1: an integer n.
Line 2: n space-separated dictionary entries.
Line 3: an integer q.
Line 4: q space-separated query strings.
Print q lines; line i is the longest dictionary entry that is a prefix of query i, or NONE.
Example 1
Input
3 cat ca dog 3 cats do dog
Expected
cat NONE dog
Explanation
cats has prefixes ca and cat in the table; the longest is cat. do has no table entry as a prefix -> NONE. dog matches dog itself.
Example 2
Input
1 a 2 apple b
Expected
a NONE
Explanation
a is a prefix of apple -> a. Nothing is a prefix of b -> NONE.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →