A DNA sequence can be modeled as a string made up of just the letters A, T, C, and G (from the nucleobases cytosine [C], guanine [G], adenine [A] and thymine [T]).In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of January 4th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #11 exercise sheet]
A DNA sequence can be modeled as a string made up of just the letters A, T, C, and G (from the nucleobases cytosine [C], guanine [G], adenine [A] and thymine [T]).
A "motif" is a recurring pattern that is thought to have some biological function, where by pattern we mean a contiguous substring (subsequence of characters).
You are helping a lab which as new machine than can very quickly sequence DNA from a tissue. The lab operator need to discover the motifs of length K that are most frequent (where by frequency we mean the number of occurrences). Multiple occurrences of a motif may overlap.
Given an integer K and a string S representing a DNA strand, you task it compute the maximum frequency of a motif of size K and how many different motifs have that frequency.
The first line of input contains an integer K, indicating the length of the motifs to consider.
The second line of input contains a string S made only of characters 'A', 'T', 'C', and 'G', representing the DNA you need to analyze.
The first line should contain a single integer the maximum frequency of a DNA motif of size K.
If there is more than one motif with that maximum frequency, the second line should contain an integer indicating how many different motifs have that maximum frequency. If there is only one motif, the second line should contain the motif itself.
The following limits are guaranteed in all the test cases that will be given to your program:
| 1 ≤ |S| ≤ 100 000 | Size of the DNA sequence | |
| 1 ≤ K ≤ min(10,|S|) | Size of the motifs |
| Example Input 1 | Example Output 1 |
3 GTATAGCGTAATAGTAG |
3 2 |
Explanation of Example Input 1
The maximum frequency of a motif of length 3 is 3 occurrences and there are 2 motifs that have this frequency:
| Example Input 2 | Example Output 2 |
4 ACACAGTATAACACACACAGCGTAATAGTACAC |
5 ACAC |
Explanation of Example Input 2
The maximum frequency of a motif of length 4 is 5 occurrences and there is only 1 motif that has this frequency: