Entraînement › Qcm Prologin 2010 › Sous-séquence

Qcm Prologin 2010 - Sous-séquence

DIFFICULTE

LIMITE DE MEMOIRE

40000 ko

LIMITE DE TEMPS

40 ms

É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 <= N <= 200000
  • 1 <= L <= 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.

    • EXEMPLE(S) D'ENTREE/SORTIE

    Exemple 1
    en entrée ...

    10
2
TCGTACGTAG
    en sortie ...
    CG

    Exemple 2
    en entrée ...

    26
4
AATTCGGCCGATCGTCGAATTCGATA
    en sortie ...
    AATT