Minimum distance between repeating substrings

Java Hard strings

Task «Minimum distance between repeating substrings»

Given a string S consisting of lowercase Latin letters. It is necessary to find the minimum distance between the starting indices of two identical non-overlapping substrings of length L, where L is the maximum possible length for which such substrings exist. If there are no identical non-overlapping substrings of length L, output -1. The distance is the difference between the starting indices of the second and first substrings. The substrings must not overlap (i.e., their intervals do not share any characters). Constraints: the length of the string is up to 10^5.

Input Format

One string S, consisting of lowercase letters of the Latin alphabet (a-z). The length of the string is from 1 to 100000.

Output Format

One integer — the minimum distance between the starting indices of two identical non-overlapping substrings of the maximum possible length L, or -1 if no such substrings exist.

Examples

Example 1

INPUT

aababc

OUTPUT

2

Example 2

INPUT

ababa

OUTPUT

2

Example 3

INPUT

abcdefg

OUTPUT

-1

main.java