АВТ
Язык:

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

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

568. Спутник

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

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

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

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

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

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

Пример

input

output

abcabcba

abcbaaabc

5

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / XI Межвузовская олимпиада 2008 /
573. H - Робот 568.
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, смена 2019 / Строки /
1990. 06 - Количество различных подстрок 568. 176. 08 - Сообщение 1991. 09 - Подпалиндромы
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, смена 2020 / Импульс-2020, строки, деревья отрезков /
1989. 02 - Поиск подстроки 568. 1990. 04 - Количество различных подстрок 1980. 05 - Число вершин 1985. 06 - Минимумы
 
время генерации 0.141 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.