Sous-séquence – Qualification 2010

Level 3

Énoncé

Une séquence d'ADN sera une suite finie constituée de lettres dans l'ensemble {A, T, G, C}. On cherche à analyser les fréquences d'apparition des sous-séquences d'une séquence d'ADN de longueur $N$ donnée en entrée. Ecrivez une fonction qui renvoie la sous-séquence contiguë de longueur $L$ de la chaîne d'ADN la plus fréquente. Dans le cas où plusieurs sous-séquences de longueur $L$ apparaissent un même nombre de fois, affichez celle qui vient en premier dans l'ordre alphabétique.

Contraintes

  • $1 \le N \le 200\ 000$
  • $1 \le L \le 15$

Entrée

  • Sur la première ligne, l'entier $N$.
  • Sur la deuxième ligne, l'entier $L$.
  • Sur la troisième ligne, la séquence d'ADN de longueur $N$.

Sortie

La sous-séquence d'ADN de longueur $L$ recherchée.

Runtime constraints

Maximum memory usage
40000 kilobytes
Maximum execution time
40 milliseconds

Input/output samples

Sample input
10
2
TCGTACGTAG
Sample output
CG
Sample input
26
4
AATTCGGCCGATCGTCGAATTCGATA
Sample output
AATT

Submit your solution

You have to register or log in to be able to submit your solution.