Все задачи
Средне Решено: 0 Процент решений: 0%

Короткие тандемные повторы в ДНК

Для каждого короткого тандемного повтора найдите самую длинную серию идущих подряд копий в последовательности ДНК.

Чему вы научитесь

  • Сравнивать подстроку с образцом
  • Считать копии, идущие подряд с заданной позиции
  • Хранить лучший результат для каждого образца

Условие

Криминалистические лаборатории сравнивают людей по коротким тандемным повторам (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 букв

Примеры

Пример 1
Ввод:
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.

Пример 2
Ввод:
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. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.