Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Суффиксы

(Время: 1 сек. Память: 16 Мб Сложность: 45%)

Назовем строкой последовательность из маленьких букв английского алфавита. Строкой, например, является пустая последовательность “”, слово “aabaf” или бесконечная последовательность букв “a”.

i-ый суффикс Si строки S – это строка S, из которой вырезаны первые i букв: так, для строки S = “aabaf” суффиксы будут такими:

S0 = “aabaf”

S1 = “abaf”

S2 = “baf”

S3 = “af”

S4 = “f”

S5 = S6 = S7 = . . . = “”

Суффиксы определены для всех i > 0.

Циклическое расширение S* конечной строки S – это строка, полученная приписыванием ее к самой себе бесконечное количество раз. Так,

S* = S0* = “aabafaabafaa...”

S1* = “abafabafabaf...”

S2* = “bafbafbafbaf...”

S3* = “afafafafafaf...”

S4* = “ffffffffffff...”

S5* = S6* = S7*= . . . = “”

По данной строке S выясните, сколько ее суффиксов Si имеют такое же циклическое расширение, как и сама строка S, то есть количество таких i, что S*= Si*.

Входные данные

Входной файл INPUT.TXT содержит строку S, состоящую не менее, чем из одной и не более, чем из 100 000 маленьких английских букв.

Выходные данные

В выходной файл OUTPUT.TXT выведите количество суффиксов строки S, имеющих такое же циклическое расширение, как и она сама.

Примеры

INPUT.TXTOUTPUT.TXT
1aa2
2ab1
3qqqq4
4xyzzyxy1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ