On donne un mot $w$, une suite de $n$ lettres minuscules de l’alphabet anglais. Pour des positions, c’est-à-dire des entiers strictement positifs $a$ et $b$ tels que $1 \le a \le b \le n$, on définit le sous-mot $w_{a,b}$ comme le mot obtenu en prenant, dans l’ordre, tous les caractères de la position $a$ à la position $b$ du mot $w$. On définit également le reste $o_{a,b}$ comme le mot obtenu en supprimant de $w$ tous les caractères de la position $a$ à la position $b$.
Trouvez la longueur du plus long sous-mot $w_{a,b}$ tel que le reste $o_{a,b}$ contienne lui aussi $w_{a,b}$ comme sous-mot.
Entrée
La première ligne contient le mot donné $w$, une suite de lettres minuscules de l’alphabet anglais.
Sortie
Affichez la plus grande longueur possible recherchée.
Sous-tâches
Soit $n$ la longueur du mot donné.
| Sous-tâche | Points | Contraintes |
|---|---|---|
| 1 | 16 | $1 \le n \le 400$ |
| 2 | 24 | $401 \le n \le 5\,000$ |
| 3 | 60 | $5001 \le n \le 100\,000$ |
Exemples
Entrée 1
abcxyzabc
Sortie 1
3
Entrée 2
bbcdbcbbcbadadda
Sortie 2
5
Remarque
Explication du deuxième exemple :
bbcdbcbbcbadadda $\rightarrow$ bbcdbcbadda