Find the Hidden Word
Time limit1sMemory limit256 MB
Given a list of known words and several messages, find which listed words occur as substrings in each message and report NO, the unique word, or AMBIGUOUS.
- Level
Medium5 of 10
- Topics
- String matching, Trie
- Solved
- No attempts yet
Problem
A white rabbit wants to send one word to a black rabbit without letting any other rabbit find out which word it is. The two rabbits agreed on a scheme beforehand, and the white rabbit handed the black rabbit the full list of words it knows. When the white rabbit sends a word, it mixes many other letters in front of the word, behind it, and around it, and sends the whole thing as one long message.
For a message, find every word on the list that occurs in the message as a contiguous substring. If exactly one distinct word occurs, that word is the one the white rabbit meant to send. Help the black rabbit answer for each message.
Input
The first line has the number of test cases (). Each test case has the following form.
- The first line has the number of words the white rabbit knows, ().
- Each of the next lines has one known word. The length of a word is at least 6 and at most 50, and a word uses lowercase English letters only.
- The next line has the number of messages the white rabbit sent, ().
- Each of the next lines has one message. The length of a message is at least 6 and at most 10000, and a message uses lowercase English letters only.
Output
Print one line for each message. First count the distinct words the white rabbit knows that occur in the message as a contiguous substring.
- If there is no such word, print NO.
- If there is exactly one, print that word as it is.
- If there are two or more, print AMBIGUOUS.