Наибольшая грань подстроки
Гранью (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).
Выходные данные
В единственной строке вывести ответ поставленной задачи.