Minimaler Abstand zwischen sich wiederholenden Teilstrings

Java Hard strings

Aufgabe «Minimaler Abstand zwischen sich wiederholenden Teilstrings»

Gegeben ist eine Zeichenkette S, die aus Kleinbuchstaben des lateinischen Alphabets besteht. Es soll der minimale Abstand zwischen den Startindizes zweier identischer, sich nicht überschneidender Teilstrings der Länge L gefunden werden, wobei L die maximal mögliche Länge ist, für die solche Teilstrings existieren. Wenn es keine identischen, sich nicht überschneidenden Teilstrings der Länge L gibt, wird -1 ausgegeben. Der Abstand ist die Differenz zwischen den Startindizes des zweiten und des ersten Teilstrings. Die Teilstrings dürfen sich nicht überschneiden (d. h. ihre Intervalle haben keine gemeinsamen Zeichen). Einschränkungen: Die Länge der Zeichenkette beträgt bis zu 10^5.

Eingabeformat

Eine Zeichenkette S, bestehend aus Kleinbuchstaben des lateinischen Alphabets (a-z). Die Länge der Zeichenkette beträgt 1 bis 100000.

Ausgabeformat

Eine ganze Zahl – der minimale Abstand zwischen den Startindizes zweier identischer, sich nicht überschneidender Teilstrings der maximal möglichen Länge L, oder -1, falls solche Teilstrings nicht existieren.

Beispiele

Beispiel 1

EINGABE

aababc

AUSGABE

2

Beispiel 2

EINGABE

ababa

AUSGABE

2

Beispiel 3

EINGABE

abcdefg

AUSGABE

-1

main.java