Задача F. Общая ДНК

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб
Максимальный балл:5  

Условие

Вам даны две строки ДНК, состоящие из символов a, g, c, t. Требуется найти их наибольшую общую подстроку. Если таких строк несколько, вывести лексикографически наименьшую.

В данной задаче требуется пройти единственный тест, который можно скачать ЗДЕСЬ

Отправка решения

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
acagaca
tcatgaca
gaca

0.073s 0.009s 17