Криминалистические лаборатории сравнивают людей по коротким тандемным повторам (STR): коротким фрагментам ДНК, например AGAT, которые много раз повторяются подряд. Для каждого фрагмента лаборатория записывает самую длинную серию идущих подряд копий во всей последовательности. В TTAGATAGATAGATCAGATAGAT фрагмент AGAT встречается трижды подряд ближе к началу и дважды подряд дальше, поэтому его результат равен 3.
Реализуйте dna_str_count(sequence, repeats).
Входные данные
sequence: последовательность ДНК из букв A, C, G и T.
repeats: фрагменты STR, которые нужно измерить.
Выходные данные
Верните по одному числу на фрагмент в том же порядке, что и в repeats: наибольшее количество копий, идущих подряд. Если фрагмент не встречается ни разу, его результат равен 0.
Ограничения
0 ≤ длина sequence ≤ 5000
1 ≤ количество фрагментов ≤ 10
Каждый фрагмент состоит из 1-8 букв
Примеры
Ввод:
sequence = "TTAGATAGATAGATCAGATAGAT"
repeats = ["AGAT", "CA"]
Ожидаемый вывод:
expected = [3, 1]
Ввод:
std::string sequence = "TTAGATAGATAGATCAGATAGAT";
std::vector<std::string> repeats = {"AGAT", "CA"};
Ожидаемый вывод:
std::vector<long long> expected = {3, 1};
Ввод:
string sequence = "TTAGATAGATAGATCAGATAGAT";
string[] repeats = new string[] {"AGAT", "CA"};
Ожидаемый вывод:
long[] expected = new long[] {3, 1};
Пояснение
AGAT повторяется 3 раза в начале и только 2 раза в конце, поэтому получает 3; CA встречается один раз и получает 1.
Ввод:
sequence = "AATGAATGAATGTATC"
repeats = ["AATG", "TATC", "GATA"]
Ожидаемый вывод:
expected = [3, 1, 0]
Ввод:
std::string sequence = "AATGAATGAATGTATC";
std::vector<std::string> repeats = {"AATG", "TATC", "GATA"};
Ожидаемый вывод:
std::vector<long long> expected = {3, 1, 0};
Ввод:
string sequence = "AATGAATGAATGTATC";
string[] repeats = new string[] {"AATG", "TATC", "GATA"};
Ожидаемый вывод:
long[] expected = new long[] {3, 1, 0};
Пояснение
AATG повторяется 3 раза, TATC один раз, а GATA ни разу: [3, 1, 0].
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
От начальной позиции прыгайте вперёд на длину фрагмента, пока следующий кусок совпадает с фрагментом.
Подсказка 2
Попробуйте каждую начальную позицию и запоминайте самую длинную серию.
Подсказка 3
Если фрагмент ни разу не совпал, лучший результат останется равным 0.
Ожидаемая сложность
время O(n × m × k), доп. память O(m)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.