Пересечение минимальных циклических сдвигов

C++ Сложный strings

Задача «Пересечение минимальных циклических сдвигов»

Даны две строки s и t, состоящие из строчных латинских букв. Необходимо найти длину наибольшей общей подстроки, которая является подстрокой некоторого циклического сдвига строки s и некоторого циклического сдвига строки t. Циклический сдвиг — это перестановка символов строки, при которой все символы смещаются на k позиций влево, а выпавшие слева символы переносятся в конец. Длина строк не превышает 10^5. Если общая подстрока не найдена, вывести 0.

Формат ввода

В первой строке дана строка s (1 ≤ |s| ≤ 10^5). Во второй строке дана строка t (1 ≤ |t| ≤ 10^5). Строки состоят только из строчных латинских букв.

Формат вывода

Выведите одно целое число — длину наибольшей общей подстроки, которая встречается в некотором циклическом сдвиге s и некотором циклическом сдвиге t.

Примеры

Пример 1

ВВОД

abc
def

ВЫВОД

0

Пример 2

ВВОД

bcd

ВЫВОД

abc

main.cpp