OpenKattis
CSI4144-19s week 06 (midterm)

Start

2019-02-20 17:15 UTC

CSI4144-19s week 06 (midterm)

End

2019-02-27 17:15 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -18039 days 9:38:21

Time elapsed

3:00:00

Time remaining

0:00:00

Problem E
Self-Similar Strings

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

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.

Output

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