eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Наибольшая грань подстроки

Наибольшая грань подстроки

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Гранью (border, verge, brink) br строки S называется любой собственный префикс этой строки, равный суффиксу S.

Строка S = abaababaabaab имеет две грани (не пустые) - ab и abaab. Строка S = abaabaab также имеет две грани - ab и abaab, но вторая грань - перекрывающаяся. Строка длины n из повторяющегося символа, например aaaaaaaa (или a^8), имеет n-1 грань. Для S = a^8 это грани: a, aa, aaa, aaaa, aaaaa, aaaaaa, aaaaaaa.

Понятие "собственный префикс" исключает грань, совпадающую с самой строкой.

Длина грани - это количество символов в ней.

Сделаем обобщение задачи. Пусть необходимо вычислить значения наибольших граней для всех подстрок S[1..i] (i=1..n) и сохранить их в массиве br[1..n].

Найдите наибольшее значение грани в массиве наибольших граней br для всех подстрок S.

Входные данные

Дана строка S (|S| ≤ 10^6).

Выходные данные

В единственной строке вывести ответ поставленной задачи.

Пример

Входные данные #1
abaabaab
Выходные данные #1
5