АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

568. C - Спутник

Ограничение времени: 1 сек.
Ограничение памяти:128000 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Две станции записали передачу со спутника, пролетающего последовательно над ними, причём первая станция записала только начало передачи, а вторая — её конец. Полученные записи сохранены в виде двух строк из символов 'a'..'z'.

Известно, что записанные фрагменты могут частично перекрываться, то есть конец первого фрагмента совпадает с началом второго, однако длина совпадения неизвестна.

Требуется найти максимально возможную длину совпадения конца первого фрагмента с началом второго.

Время тестирования: 1 секунда на один тест

В первой строке входного файла содержится информация, принятая первой станицей, во второй строке — информация, принятая второй станцией. Длина каждой строки не превосходит 100 000 символов. Строки содержат только строчные латинские буквы.

Выведите в выходной файл максимально возможную длину совпадения.

Пример

input

output

abcabcba

abcbaaabc

5

 


Статистика Послать на проверку Обсуждение задачи Автор/источник: Игорь Андрианов, XI Межвузовская олимпиада, Вологда
Задачи с соревнований / Межвузовские олимпиады / XI Межвузовская олимпиада 2008 /
567. B - Память 568. 569. D - Дерево 570. E - Снукер 571. F - Суперпалиндромы
 
время генерации 0.094 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.