Блоком рядка \(Т\) в позиції і назвемо найбільший підрядок в \(T\), який починається в позиції і та співпадає з префіксом цього рядка . Довжина блоку в позиції 0 рівна нулю. Необхідно знайти довжину найбільшого блоку заданого рядка \(Т\).
Формат вхідних даних
Єдиний рядок вхідного стандартного потоку містить рядок \(Т\) \((1 ≤ size(Т) ≤ 10^5)\)- усі символи якого - це літери латиниці.
Формат вихідних даних
У єдиний рядок вихідного стандартного потоку вивести одне число – довжину найбільшого блоку.
Приклад вхідних даних
abaabaab
Приклад вихідних даних
5
Коментарі