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

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

1 секунда
64 мегабайта
Very easy

Бордер (также называемый краем или границей) строки — это любой собственный префикс строки, который равен суффиксу .

Например, строка 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 и сохранить их в массиве .

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

Input

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

Output

Выведите одно число — ответ на задачу.

Examples

Example 1

Loading
Loading