Задача
Некоторые вирусы реплицируются путем замены фрагмента ДНК в живой клетке фрагментом ДНК, который вирус несет с собой. Это заставляет клетку создавать вирусы, идентичные оригинальной, зараженной клеткой. Группа биологов заинтересована в том, чтобы узнать, сколько ДНК вносит вирус в геном хозяина. Чтобы узнать об этом, они упорядочили полный геном здоровой клетки, а также идентичную клетку, инфицированную вирусом.
Геном оказался довольно большим, поэтому теперь им нужна Ваша помощь на этапе обработки данных. Имея последовательность ДНК до и после вирусной инфекции, определите длину самой маленькой одной последовательной части ДНК, которая может быть вставлена в первую последовательность, чтобы превратить ее во вторую. Один последовательный фрагмент ДНК также может быть удален из того же положения в последовательности, куда был вставлен ДНК. Небольшие изменения в ДНК могут иметь большие эффекты, поэтому вирус может вставить только несколько букв или даже ничего.
Входные данные
Состоит из двух строк, содержащих последовательность ДНК до и после вирусной инфекции, соответственно. Последовательность ДНК задается как строка, содержащая от 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.