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