An object is sometimes called ‘self-similar’ if there are parts of it that are repeated in other places within the same object. Fractals are self-similar mathematical objects, where the similarities occur at different sizes.
Here, we’ll consider ‘self-similar strings.’ We’ll say that a string $s$ is self-similar to degree $d$ if all $d$-length substrings of $s$ occur in at least one other location in $s$. For example, the string ‘babbabb’ is self-similar to degree 0, degree 1, and degree 2. It is not self-similar to any greater degree. It should be clear that $d \leq |s|-1$.
Write a program which determines the largest degree of self-similarity for given strings.
Input is a list of up to 10000 strings, one per line. Each string is made of up to 80 lower-case alphabet characters (a-z). Input ends at the end of file.
For each string, print the largest degree to which the string is self-similar.
|Sample Input 1||Sample Output 1|
abcdefg aaaaaa bababab aaabbbccc
0 5 4 1