Distância mínima entre substrings repetidas

Java Hard strings

Tarefa «Distância mínima entre substrings repetidas»

Dada uma string S composta por letras minúsculas do alfabeto latino. É necessário encontrar a distância mínima entre os índices iniciais de duas substrings idênticas e não sobrepostas de comprimento L, onde L é o maior comprimento possível para o qual tais substrings existem. Se não houver substrings idênticas e não sobrepostas de comprimento L, imprimir -1. A distância é a diferença entre os índices iniciais da segunda e da primeira substring. As substrings não devem se sobrepor (ou seja, seus intervalos não possuem caracteres em comum). Restrições: comprimento da string de até 10^5.

Formato de Entrada

Uma única string S composta por letras minúsculas do alfabeto latino (a-z). O comprimento da string varia de 1 a 100000.

Formato de Saída

Um único número inteiro — a distância mínima entre os índices iniciais de duas substrings idênticas e não sobrepostas de comprimento máximo possível L, ou -1 se tais substrings não existirem.

Exemplos

Exemplo 1

ENTRADA

aababc

SAÍDA

2

Exemplo 2

ENTRADA

ababa

SAÍDA

2

Exemplo 3

ENTRADA

abcdefg

SAÍDA

-1

main.java