Contact
Contact
Contact
Contact
Dr. Astro Insky works at a radiotelescope centre. Recently, she noticed a very curious microwave pulsing emission sent right from the centre of the galaxy. Is the emission transmitted by some extraterrestrial form of intelligent life? Or is it nothing but the usual heartbeat of the stars?
Output Data
A report in file CONTACT.OUT with at most N lines, listing the at most N greatest frequencies and corresponding patterns. The listing must be produced in decreasing order of pattern frequency, and consists of lines formatted like frequency pattern pattern pattern where frequency is the number of occurrences of the patterns that follow. The patterns in each line must appear in decreasing order of length. Patterns of equal length must be listed in reverse numerical order. In case there are less than N distinct frequencies, the output listing will have less than N lines.
Task
You must help Dr. Insky to find out the truth by providing a tool to analyse bit patterns in the files she records. Dr. Insky wants to find the patterns of length between (and including) A and B that repeat themselves most often in the data file of each day. In each case, the greatest N distinct frequencies (that is, number of occurrences) are sought. Pattern occurrences may overlap, and only patterns that occur at least once are taken into account.
Constraints
The input file may have up to 2 megabytes. The parameters A, B and N are constrained by: 0 < N 20 0 < A B 12
Sample Input:
2 4 10 0101001001000100011110110000101 0011001111000010010011110010000 0002 This asks for the top ten frequencies of patterns of length between two and four that occur in the bit pattern 0101001001000100011110110000101 0011001111000010010011110010000 000 Note that the fourth line of the input file above appears split in order to fit herein. In this example, pattern 100 occurs 12 times, and