"Are there Trolls in your forest?" asks Alice.
"Yes there are, and many of them," answers the fairy.
"But I don't see any."
"You don't know how do they look like, Alice. They are afraid of you
so they have changed their appearance."
"How do they look like?" inquires Alice.
"Here's my magic forest. It's a sequence of letters:
'rabbittreebugabbitreetreerabbinrabbit'. A Troll is some subsequence
of it. Try a guess!"
"Are the Trolls hiding as 'bug's?"
"No, but I'll give you a hint: there are more Trolls than 'bug's in my forest."
"Are the Trolls hiding as 'tree's?"
"No, there are fewer Trolls then 'tree's."
"Then those 'rabbit's are Trolls," suggests Alice with a smile.
"Yes, those 'rabbit's."
Your task is to help Alice with some larger forests she visited later. The forests are sequences of letters given to you as an input. You have to guess what subsequence in the forest is a Troll. The fairy (in our case substituted by the IPSC on-line judge) will give you one of these answers to your submitted guess:
The first answer means your guess was correct, you have solved the problem. For the second two answers the fairy counts the number of occurrences of the sequence 'yourguess' in the forest and compares it to the number of occurrences of the Troll sequence and gives the correct answer. The occurrences may overlap. There is no other sequence that appears in the forest the same number of times as the Troll sequence. Remember that you have only 10 guesses for each input.
The input file contains a sequence of lower case letters that is divided into lines of no more than 78 characters. Whitespace characters should be ignored. The given sequence is the forest.
The output file contains a single word that is the guessed Troll sequence.
rabbittreebugabbitreetreerabbinrab bitOutput file:
rabbit