Бордер (также называемый краем или границей) строки — это любой собственный префикс строки, который равен суффиксу .
Например, строка S = \text{abaababaabaab} имеет два (непустых) бордера: и . Строка S = \text{abaabaab} также имеет два бордера: и , но второй бордер перекрывается. Строка длины , состоящая из повторяющегося символа, например, (или a^8), имеет n-1 бордеров. Для S = a^8 ее бордеры: \text{a}, \text{aa}, \text{aaa}, \text{aaaa}, \text{aaaaa}, \text{aaaaaa}, \text{aaaaaaa}.
Понятие «собственного префикса» исключает бордер, совпадающий со всей строкой.
Длина бордера — это количество символов в нем.
Обобщим задачу. Предположим, вам нужно вычислить значения наибольших бордеров для всех префиксов для i = 1..n и сохранить их в массиве .
Найдите максимальное значение бордера в массиве для всех префиксов .
Дана строка (|S| \leq 10^6).
Выведите одно число — ответ на задачу.
Example 1