Gegeben sei ein Wort $w$, eine Folge von $n$ englischen Kleinbuchstaben. Für gegebene Positionen, also positive ganze Zahlen $a$ und $b$ mit $1 \le a \le b \le n$, definieren wir das Teilwort $w_{a,b}$ als das Wort, das entsteht, wenn wir alle Zeichen von der $a$-ten bis zur $b$-ten Position in $w$ der Reihe nach nehmen. Außerdem definieren wir den Rest $o_{a,b}$ als das Wort, das entsteht, wenn wir aus $w$ alle Zeichen von der $a$-ten bis zur $b$-ten Position löschen.
Finden Sie die Länge des längsten Teilworts $w_{a,b}$, für das der Rest $o_{a,b}$ ebenfalls $w_{a,b}$ als Teilwort enthält.
Eingabe
Die erste Zeile enthält das gegebene Wort $w$, eine Folge englischer Kleinbuchstaben.
Ausgabe
Geben Sie die gesuchte größtmögliche Länge aus.
Teilaufgaben
Sei $n$ die Länge des gegebenen Wortes.
| Teilaufgabe | Punkte | Beschränkungen |
|---|---|---|
| 1 | 16 | $1 \le n \le 400$ |
| 2 | 24 | $401 \le n \le 5\,000$ |
| 3 | 60 | $5001 \le n \le 100\,000$ |
Beispiele
Eingabe 1
abcxyzabc
Ausgabe 1
3
Eingabe 2
bbcdbcbbcbadadda
Ausgabe 2
5
Hinweis
Erklärung des zweiten Beispiels: bbcdbcbbcbadadda → bbcdbcbadda