Sous-séquence – Qualification 2010

Niveau 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.

Contraintes d'exécution

Utilisation mémoire maximum
40000 kilo-octets
Temps d'exécution maximum
40 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
10
2
TCGTACGTAG
Exemple de sortie
CG
Exemple d'entrée
26
4
AATTCGGCCGATCGTCGAATTCGATA
Exemple de sortie
AATT