Problem: Anagram Solver

Want to try solving this problem? You can submit your code online if you log in or register.

Anagram Solver

Input Files: anagin.txt, words.txt
Output File: anagout.txt
Time Limit: 1.5 seconds

As the Morality Observational Liaison Employee for your school, you have noticed that lately students have been passing more and more notes around class. It is your task to intercept these notes and ensure that they do not smack of subversive activity. There has been talk in the staff tea room of a student uprising within the school, and the teachers are in the grip of terror. You are on the case.

Recently, you have made a horrifying discovery. You saw two students looking at you and laughing on sports day, and so you quickly and efficiently plucked the following note out of their hands: "what an awful relay this". You ran your fingers through your new perm as you studied the seemingly innocent note, and then it hit you. They were using anagrams! Upon rearranging the last two words, the note read "what an awful hairstyle". You blushed, scrunched up the note and hid behind a tree as you contemplated this shocking new discovery.

There was only one solution. Every note in your possession had to be carefully tested for the use of anagrams. It would take far too long by hand, and you had never been good at English. So you sat down to write a computer program that would look for key words that might have been encrypted within the students' notes.

The program will read in a list of subversive words from the file words.txt and will read in fragments of notes from the file anagin.txt. You must test each note fragment to see if it is an anagram of any subversive word.

Input

The list of subversive words (words.txt) will consist of a sequence of lines with one word on each line. All words will be at most 30 letters long, will contain no punctuation and will be entirely in lower case. This list will contain at most 650 words and will be terminated by a line containing a single # character. No two subversive words will be the same.

The input file (anagin.txt) will consist of a sequence of lines with one or more words on each line. Words on the same line will be separated by a single space. Each line will be no more than 80 characters long, will contain no punctuation and will be entirely in lower case. This list of lines will also be terminated by a line containing a single # character. There will be at most 200,000 lines.

Output

For each line in the input file, a line of output must be produced containing a list of all subversive words which are anagrams of the entire line from the input file. These words must be separated by a single space, and may be output in any order on the line. If there is no such subversive word, the output line should be "No anagram found". Do not produce any output for the final #.

Note that each anagram found should use only one subversive word, and should use the entire line from the input file.

Sample words.txt 1

the
quality
of
mercy
is
not
strained
#

Sample anagin.txt 1

cry me
a river
#

Sample Output 1

mercy
No anagram found

Sample words.txt 2

evil
uprising
vile
hairstyle
revolution
takeover
#

Sample anagin.txt 2

what an awful
relay this
live
sports
what an awful relay this
live this relay
#

Sample Output 2

No anagram found
hairstyle
evil vile
No anagram found
No anagram found
No anagram found

Scoring

The score for each line of the input file will be determined as follows:

If no anagram exists, a score of 100% will be given if the program determines that no anagram exists, and 0% otherwise.
If n anagrams exist:
- If the program determines that no anagram exists, a score of 0% will be given.
- If the program produces m of these anagrams, as well as w words that are not actually anagrams, the score will be (m-w)/n x 100%, down to a minimum score of 0%.
In particular, if all possible anagrams are produced with nothing extraneous then the score will be 100%.

For instance, consider Sample Input 2 with the input line "live". There are n=2 anagrams of this line in words.txt. The output line

evil vile uprising

would obtain a score of (2-1)/2 x 100% = 50%, and the output line

vile

would obtain a score of (1-0)/2 x 100% = 50%.