Distance minimale entre des sous-chaînes répétées

Java Hard strings

Tâche «Distance minimale entre des sous-chaînes répétées»

Étant donné une chaîne S composée de lettres minuscules de l'alphabet latin. Il faut trouver la distance minimale entre les indices de début de deux sous-chaînes identiques non chevauchantes de longueur L, où L est la longueur maximale possible pour laquelle de telles sous-chaînes existent. S'il n'existe pas de sous-chaînes identiques non chevauchantes de longueur L, afficher -1. La distance est la différence entre les indices de début de la deuxième et de la première sous-chaîne. Les sous-chaînes ne doivent pas se chevaucher (c'est-à-dire que leurs intervalles n'ont pas de caractères communs). Contraintes : longueur de la chaîne jusqu'à 10^5.

Format d\ entrée

Une seule chaîne S, composée de lettres minuscules de l'alphabet latin (a-z). Longueur de la chaîne de 1 à 100000.

Format de sortie

Un seul nombre entier — la distance minimale entre les indices de début de deux sous-chaînes identiques non chevauchantes de longueur maximale possible L, ou -1 si de telles sous-chaînes n'existent pas.

Exemples

Exemple 1

ENTRÉE

aababc

SORTIE

2

Exemple 2

ENTRÉE

ababa

SORTIE

2

Exemple 3

ENTRÉE

abcdefg

SORTIE

-1

main.java