The biggest border of the substring
The border (verge, brink) br of the string S is any proper prefix of this string that is equal to the suffix of S.
A string S = abaababaabaab has two borders (not empty) - ab and abaab. A string S = abaabaab has two borders - ab and abaab, but the second one is overlapping. A string of length n formed with a repeating character, like aaaaaaaa (or a^8), has n-1 borders. For S = a^8 the borders are: a, aa, aaa, aaaa, aaaaa, aaaaaa, aaaaaaa.
The concept of "proper prefix" eliminates the border equals to the string.
The length of the border is the number of characters in it.
We make a generalization of the problem. Suppose we want to calculate the values of the largest borders for all substrings of S[1..i] (i = 1..n) and store them in the array br[1..n].
Find the maximum value of the border in array of the largest borders br for all substrings in S.
Input
Given a string S (|S| ≤ 10^6).
Output
Print one number - the answer to the problem.