Problem
Rechtsmedizinische Labore vergleichen Menschen anhand von Short Tandem Repeats (STRs): kurzen DNA-Abschnitten wie AGAT, die viele Male direkt hintereinander vorkommen. Für jeden Abschnitt notiert das Labor die längste Folge aufeinanderfolgender Kopien irgendwo in der Sequenz. In TTAGATAGATAGATCAGATAGAT kommt AGAT am Anfang dreimal hintereinander vor und später zweimal, sein Wert ist also 3.
Implementiere dna_str_count(sequence, repeats).
Eingabe
sequence: Die DNA-Sequenz aus den Buchstaben A, C, G und T.
repeats: Die STR-Abschnitte, die gemessen werden sollen.
Ausgabe
Gib pro Abschnitt einen Wert zurück, in derselben Reihenfolge wie in repeats: die größte Zahl von Kopien, die direkt hintereinander vorkommen. Ein Abschnitt, der nie vorkommt, hat den Wert 0.
Einschränkungen
0 ≤ Länge von sequence ≤ 5000
1 ≤ Anzahl der Abschnitte ≤ 10
Jeder Abschnitt hat 1 bis 8 Buchstaben
Beispiele
Eingabe:
sequence = "TTAGATAGATAGATCAGATAGAT"
repeats = ["AGAT", "CA"]
Erwartete Ausgabe:
expected = [3, 1]
Eingabe:
std::string sequence = "TTAGATAGATAGATCAGATAGAT";
std::vector<std::string> repeats = {"AGAT", "CA"};
Erwartete Ausgabe:
std::vector<long long> expected = {3, 1};
Eingabe:
string sequence = "TTAGATAGATAGATCAGATAGAT";
string[] repeats = new string[] {"AGAT", "CA"};
Erwartete Ausgabe:
long[] expected = new long[] {3, 1};
Erläuterung
AGAT steht am Anfang dreimal und am Ende nur zweimal hintereinander, also bekommt es 3; CA kommt einmal vor und bekommt 1.
Eingabe:
sequence = "AATGAATGAATGTATC"
repeats = ["AATG", "TATC", "GATA"]
Erwartete Ausgabe:
expected = [3, 1, 0]
Eingabe:
std::string sequence = "AATGAATGAATGTATC";
std::vector<std::string> repeats = {"AATG", "TATC", "GATA"};
Erwartete Ausgabe:
std::vector<long long> expected = {3, 1, 0};
Eingabe:
string sequence = "AATGAATGAATGTATC";
string[] repeats = new string[] {"AATG", "TATC", "GATA"};
Erwartete Ausgabe:
long[] expected = new long[] {3, 1, 0};
Erläuterung
AATG wiederholt sich dreimal, TATC einmal und GATA nie: [3, 1, 0].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Spring von einer Startposition aus immer um die Länge des Abschnitts weiter, solange das nächste Stück dem Abschnitt entspricht.
Hinweis 2
Probiere jede Startposition aus und merk dir die längste Folge.
Hinweis 3
Passt ein Abschnitt nie, bleibt der beste Wert bei 0.
Erwartete Komplexität
Zeit O(n × m × k), zusätzlicher Speicher O(m)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.