Задача
Некоторые вирусы реплицируются путем замены фрагмента ДНК в живой клетке фрагментом ДНК, который вирус несет с собой. Это заставляет клетку создавать вирусы, идентичные оригинальной, зараженной клеткой. Группа биологов заинтересована в том, чтобы узнать, сколько ДНК вносит вирус в геном хозяина. Чтобы узнать об этом, они упорядочили полный геном здоровой клетки, а также идентичную клетку, инфицированную вирусом.
Геном оказался довольно большим, поэтому теперь им нужна Ваша помощь на этапе обработки данных. Имея последовательность ДНК до и после вирусной инфекции, определите длину самой маленькой одной последовательной части ДНК, которая может быть вставлена в первую последовательность, чтобы превратить ее во вторую. Один последовательный фрагмент ДНК также может быть удален из того же положения в последовательности, куда был вставлен ДНК. Небольшие изменения в ДНК могут иметь большие эффекты, поэтому вирус может вставить только несколько букв или даже ничего.
Входные данные
Состоит из двух строк, содержащих последовательность ДНК до и после вирусной инфекции, соответственно. Последовательность ДНК задается как строка, содержащая от 1 до $10^5$ букв верхнего регистра из алфавита {A, G, C, T}.
Выходные данные
Выведите одно целое число — минимальную длину ДНК, вставленную вирусом.
Тесты
| № | Входные данные | Выходные данные |
| 1 | AAAAA AGCGAA |
3 |
| 2 | GTTTGACACACATT GTTTGACCACAT |
4 |
| 3 | SMMSMM SMAHMA |
4 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <iostream> #include <cstring> using namespace std; int main() { //Инициализируем массивы, удовлетворяющие условия char b[100001], a[100001]; cin >> b >> a; // b-строка до (before), a-строка после (after) int s = 0, l1 = strlen(b), l2 = strlen(a), e1 = l1, e2 = l2; //определяем длины первой и второй строк, без учёта нуль-символа. // Проверяем есть ли символ в массиве b[s], // Если есть и он такой же, как и в массиве a[s] - счётчик увеличивается // в результате мы узнаём на каком, крайнем слева, символе начинаются расхождения (s) for (; b[s] && b[s] == a[s]; ++s); // Цикл проходиться по массиву a и b с конца введённых в них строк // Цикл двигается по массиву до первого расхождения в буквах (b[e1]!=a[e2]) // в результате мы узнаём на каком, крайнем справа, символе начинаются расхождения (e2) for (; e1>=0 && e2>=0 && b[e1]==a[e2]; --e1, --e2); // Считаем максимальное количество букв, которые подверглись расхождению, ища максимальное от // максимального между 0 и разницей в кол-ве символов второй строки от первой и // разницей между крайним правым и крайним левым номером элемента на котором начались расхождения + 1 cout << max(max(0,l2-l1),e2-s+1) << endl; } |
Решение
Нам нужно определить длину самой маленькой одной последовательной части ДНК, которая может быть вставлена в первую последовательность, чтобы превратить ее во вторую.
В циклах for мы узнаём крайний слева и справа элемент обоих массивов, на которых буквы первой строки начинают не совпадать с буквами второй, s и e2 соответственно. Чтобы узнать результат необходимо проверить является ли l2 > l1 и больше ли l2-l1 чем e2-s1+1.
— Нет, метки не ваша сильная сторона. Вы думаете это задача на изучения вирусов? Или важно, что вы увидели ее на е-олимпе? О чем задача? Какая основная идея алгоритма?
— Для первого раза пересказ кода русскими буквами еще простителен, но вы делаете это системой. Вам нужно описать алгоритм. Комментариев, которые в программе уже даже много для пояснения. В решении нужно коротко и без деталей реализации описать алгоритм.
— «нулевой элемент» это это элемент с номером 0. А первый — с номером 1. Там еще много всяких «ища» и «подверглись расхождению». Попробуйте, пожалуйста, выражаться проще. Не такая уж сложная программа.
Что бы стало яснее, что я от вас ожидаю, я открыл первую попавшуюся работу — https://cpp.mazurok.com/e-olymp-1342/. Посмотрите, как там описан алгоритм.
> В тексте решения ошибка кодирования символа «>» в подстроке » l2 > l1″
> Оформление кода: нет пробелов после «(» и перед «)», слишком длинные строки
— Что-то тут не так «>»
— В описании Вы опять что-то пишите про циклы и вычитаете какие-то переменные. Вы опять объясняете программу. Пожалуйста, не объясняйте программу. Она очень простая. Там совсем нечего объяснять. Давайте, я попробую Вам помочь.
0. Четко написать что из первой строки сначала удаляют какой-то непрерывный кусок, а потом на это место вставляют другой. Фактически это замена одной подстроки на другую. Автор это на этом не акцентирует внимание.
1. Нужно для каждого теста показать как он получился — что удалили из первой строки и что туда добавили.
2. Далее вы находите совпадающие префиксы (начало) и совпадающие суффиксы (окончание) строк.
3. Все, кроме этих суффиксов и префиксов из первой строки будет удалено.
4. Все, кроме этих суффиксов и префиксов из второй строки будет вставлено в первую. Нас интересует именно длина этой подстроки.
Попробуйте, пожалуйста, составить описание своего алгоритма в каком-то таком стиле.
— Если на каникулах будет время, давайте приведем в порядок код. Пожалуйста, замените циклы for на while.
— Во втором цикле обойдитесь, пожалуйста, одной переменной — расстоянием от конца строк.