e-olymp
Змагання

Programming Principles 1. Week 6. October 7 - 13. PART 2

Репликация вируса

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

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

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

Состоит из двух строк, содержащих последовательность ДНК до и после вирусной инфекции, соответственно. Последовательность ДНК задается как строка, содержащая от 1 до 105 букв верхнего регистра из алфавита {A, G, C, T}.

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
AAAAA
AGCGAA
Вихідні дані #1
3
Вхідні дані #2
GTTTGACACACATT
GTTTGACCACAT
Вихідні дані #2
4
Джерело 2013 ACM Nordic (NCPC), Октябрь 5, Задача D