| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 15 | 3 | 3 | 20.000% |
Недавно Альберт Моисеевич обновил свой iPad до iOS 8.1. И, недолго думая, он установил новую игру, вышедшую буквально вчера.
Суть игры довольно проста: дана строка $s,ドル состоящая из строчных латинских символов. Игроку предлагается за отведенное время найти в ней подстроку, у которой существует максимальное количество непересекающихся вхождений в строку $s$. Вхождением подстроки $t$ в строку $s$ будем называть пару символов ($l,ドル $r$), такую, что $l \le r$ и подстрока строки $s$ с $l$ по $r$ символ включительно равна строке $t$. Непересекающимися будем называть два вхождения ($l_1, r_1$) и ($l_2, r_2$), такие, что отрезок $[l_1, r_1]$ не пересекается с отрезком $[l_2, r_2]$.
За найденную подстроку игроку начисляется количество очков, равное ее длине. Альберт Моисеевич хочет набрать как можно больше очков, поэтому он просит вас найти подстроку максимальной длины, которая будет удовлетворять описанному условию. Помогите ему!
В первой и единственной строке входного дана строка $s$ (1ドル \le |s| \le 10^5$), состоящая только и строчных латинских букв.
В единственной строке выходного файла выведите максимальную длину подстроки, которая удовлетворяет условию.
abacaba
1
abab
2