Tutte le sfide
Media 0 risolte 0% di accettazione

Ripetizioni in tandem nel DNA (STR)

Per ogni breve ripetizione in tandem, trova la sequenza più lunga di copie consecutive in una sequenza di DNA.

Cosa imparerai

  • Confrontare una sottostringa con un pattern
  • Contare le copie consecutive a partire da una posizione
  • Conservare il conteggio migliore per ogni pattern

Problema

I laboratori di genetica forense confrontano le persone tramite le brevi ripetizioni in tandem (STR, short tandem repeats): brevi unità di DNA, come AGAT, che compaiono molte volte di seguito. Per ogni unità, il laboratorio registra il numero massimo di copie consecutive presenti in un punto qualsiasi della sequenza. In TTAGATAGATAGATCAGATAGAT l'unità AGAT compare tre volte di seguito verso l'inizio e due volte più avanti, quindi il suo conteggio è 3.

Implementa dna_str_count(sequence, repeats).

Input

sequence: la sequenza di DNA, composta dalle lettere A, C, G e T.

repeats: le unità STR da misurare.

Output

Restituisci un conteggio per ogni unità, nello stesso ordine di repeats: il numero massimo di copie che compaiono una dopo l'altra. Un'unità che non compare mai ha conteggio 0.

Vincoli

0 ≤ lunghezza di sequence ≤ 5 000

1 ≤ numero di unità ≤ 10

Ogni unità ha da 1 a 8 lettere

Esempi

Esempio 1
Input:
sequence = "TTAGATAGATAGATCAGATAGAT"
repeats = ["AGAT", "CA"]

Output atteso:
expected = [3, 1]
Input:
std::string sequence = "TTAGATAGATAGATCAGATAGAT";
std::vector<std::string> repeats = {"AGAT", "CA"};

Output atteso:
std::vector<long long> expected = {3, 1};
Input:
string sequence = "TTAGATAGATAGATCAGATAGAT";
string[] repeats = new string[] {"AGAT", "CA"};

Output atteso:
long[] expected = new long[] {3, 1};

Spiegazione

AGAT si ripete 3 volte all'inizio e solo 2 alla fine, quindi vale 3; CA compare una volta, quindi vale 1.

Esempio 2
Input:
sequence = "AATGAATGAATGTATC"
repeats = ["AATG", "TATC", "GATA"]

Output atteso:
expected = [3, 1, 0]
Input:
std::string sequence = "AATGAATGAATGTATC";
std::vector<std::string> repeats = {"AATG", "TATC", "GATA"};

Output atteso:
std::vector<long long> expected = {3, 1, 0};
Input:
string sequence = "AATGAATGAATGTATC";
string[] repeats = new string[] {"AATG", "TATC", "GATA"};

Output atteso:
long[] expected = new long[] {3, 1, 0};

Spiegazione

AATG si ripete 3 volte, TATC una volta e GATA mai: [3, 1, 0].

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

Da una posizione di partenza, continua ad avanzare della lunghezza dell'unità finché il pezzo successivo coincide con l'unità.

Suggerimento 2

Prova ogni posizione di partenza e ricorda la serie più lunga.

Suggerimento 3

Se un'unità non corrisponde mai, il conteggio migliore resta 0.

Complessità attesa

tempo O(n × m × k), spazio aggiuntivo O(m)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.