Две станции
записали передачу со спутника, пролетающего последовательно над ними, причём
первая станция записала только начало передачи, а вторая — её конец. Полученные
записи сохранены в виде двух строк из символов 'a'..'z'.
Известно, что
записанные фрагменты могут частично перекрываться, то есть конец первого
фрагмента совпадает с началом второго, однако длина совпадения неизвестна.
Требуется
найти максимально возможную длину совпадения конца первого фрагмента с началом
второго.
Время
тестирования: 1 секунда на один тест
В первой
строке входного файла содержится информация, принятая первой
станицей, во второй строке — информация, принятая второй станцией. Длина каждой
строки не превосходит 100 000 символов. Строки содержат только строчные
латинские буквы.
Выведите в выходной
файл максимально возможную длину совпадения.
Пример
|
input
|
output
|
|
abcabcba
abcbaaabc
|
5
|
