Сейчас Эркюль Пуаро занят разоблачением международного преступного синдиката, занимающегося контрабандой предметов искусства. Полиция, сотрудничающая с Пуаро, перехватила зашифрованное письмо, содержащее информацию о месте и времени предстоящей сделки, на которой будет присутствовать и глава синдиката. Для того, чтобы чтобы сорвать сделку и задержать главу синдиката, необходимо расшифровать перехваченное письмо.
Эркюль знает, что ключ к шифру вычисляется из строки s. Обозначим за f(w) длину максимального суффикса w, не равного w, который является и префиксом w. Например, ,
,
. Тогда, ключом является максимум по всем t, являющимися подстроками s, (|t| + f(t)2). Помогите Эркюлю вычислить ключ.
В единственной строке дана строка s, состоящая из строчный латинских букв (1 ≤ |s| ≤ 500 000).
Выведите единственное целое число — искомый ключ к шифру.
ababaab
14