eolymp
bolt
Try our new interface for solving problems
Məsələlər

Замечательные подстроки

Замечательные подстроки

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 512 MiB

Пусть S - строка, состоящая из прописных букв английского алфавита. Непустая строка T называется замечательной ранга k по отношению к S, если строка k·T = T + T + ... + T (строка T повторяется k раз) является подстрокой S. Более формально S = U + k·T + V, где U и V некоторые (возможно пустые) строки.

Задана строка S. Найдите наибольший возможный ранг x такой, что существует строка T, являющаяся замечательной строкой ранга x по отношению к S.

Giriş verilənləri

Строка S (1 |S| 10^6), состоящая только из прописных букв английского алфавита.

Çıxış verilənləri

Вывести одно число: максимальный ранг замечательной строки по отношению к S.

Nümunə

Giriş verilənləri #1
aaabc
Çıxış verilənləri #1
3
Mənbə 2013 Петрозаводск, MIPT contest, Август 25, Задача G