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.
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.
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 "
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.
the quality of mercy is not strained #
cry me a river #
mercy No anagram found
evil uprising vile hairstyle revolution takeover #
what an awful relay this live sports what an awful relay this live this relay #
No anagram found hairstyle evil vile No anagram found No anagram found No anagram found
The score for each line of the input file will be determined as follows:
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
would obtain a score of (1-0)/2 x 100% = 50%.