e-olymp 6253. Репликация вируса

Задача

Некоторые вирусы реплицируются путем замены фрагмента ДНК в живой клетке фрагментом ДНК, который вирус несет с собой. Это заставляет клетку создавать вирусы, идентичные оригинальной, зараженной клеткой. Группа биологов заинтересована в том, чтобы узнать, сколько ДНК вносит вирус в геном хозяина. Чтобы узнать об этом, они упорядочили полный геном здоровой клетки, а также идентичную клетку, инфицированную вирусом.

Геном оказался довольно большим, поэтому теперь им нужна Ваша помощь на этапе обработки данных. Имея последовательность ДНК до и после вирусной инфекции, определите длину самой маленькой одной последовательной части ДНК, которая может быть вставлена в первую последовательность, чтобы превратить ее во вторую. Один последовательный фрагмент ДНК также может быть удален из того же положения в последовательности, куда был вставлен ДНК. Небольшие изменения в ДНК могут иметь большие эффекты, поэтому вирус может вставить только несколько букв или даже ничего.

Входные данные

Состоит из двух строк, содержащих последовательность ДНК до и после вирусной инфекции, соответственно. Последовательность ДНК задается как строка, содержащая от 1 до $10^5$ букв верхнего регистра из алфавита {AGCT}.

Выходные данные

Выведите одно целое число — минимальную длину ДНК, вставленную вирусом.

Тесты

Входные данные Выходные данные
1 AAAAA
AGCGAA
3
2 GTTTGACACACATT
GTTTGACCACAT
4
3 SMMSMM
SMAHMA
4

Код

Решение

Нам нужно определить длину самой маленькой одной последовательной части ДНК, которая может быть вставлена в первую последовательность, чтобы превратить ее во вторую.

В циклах for мы узнаём крайний слева и справа элемент обоих массивов, на которых буквы первой строки начинают не совпадать с буквами второй, s и e2 соответственно. Чтобы узнать результат необходимо проверить является ли l2 > l1 и больше ли l2-l1 чем e2-s1+1.

3 thoughts on “e-olymp 6253. Репликация вируса

  1. — Нет, метки не ваша сильная сторона. Вы думаете это задача на изучения вирусов? Или важно, что вы увидели ее на е-олимпе? О чем задача? Какая основная идея алгоритма?
    — Для первого раза пересказ кода русскими буквами еще простителен, но вы делаете это системой. Вам нужно описать алгоритм. Комментариев, которые в программе уже даже много для пояснения. В решении нужно коротко и без деталей реализации описать алгоритм.
    — «нулевой элемент» это это элемент с номером 0. А первый — с номером 1. Там еще много всяких «ища» и «подверглись расхождению». Попробуйте, пожалуйста, выражаться проще. Не такая уж сложная программа.
    Что бы стало яснее, что я от вас ожидаю, я открыл первую попавшуюся работу — https://cpp.mazurok.com/e-olymp-1342/. Посмотрите, как там описан алгоритм.

  2. > В тексте решения ошибка кодирования символа «>» в подстроке » l2 > l1″
    > Оформление кода: нет пробелов после «(» и перед «)», слишком длинные строки

  3. — Что-то тут не так «&gt»
    — В описании Вы опять что-то пишите про циклы и вычитаете какие-то переменные. Вы опять объясняете программу. Пожалуйста, не объясняйте программу. Она очень простая. Там совсем нечего объяснять. Давайте, я попробую Вам помочь.
    0. Четко написать что из первой строки сначала удаляют какой-то непрерывный кусок, а потом на это место вставляют другой. Фактически это замена одной подстроки на другую. Автор это на этом не акцентирует внимание.
    1. Нужно для каждого теста показать как он получился — что удалили из первой строки и что туда добавили.
    2. Далее вы находите совпадающие префиксы (начало) и совпадающие суффиксы (окончание) строк.
    3. Все, кроме этих суффиксов и префиксов из первой строки будет удалено.
    4. Все, кроме этих суффиксов и префиксов из второй строки будет вставлено в первую. Нас интересует именно длина этой подстроки.
    Попробуйте, пожалуйста, составить описание своего алгоритма в каком-то таком стиле.
    — Если на каникулах будет время, давайте приведем в порядок код. Пожалуйста, замените циклы for на while.
    — Во втором цикле обойдитесь, пожалуйста, одной переменной — расстоянием от конца строк.

Добавить комментарий