Суффиксы
(Время: 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.TXT | OUTPUT.TXT |
|---|
| 1 | aa | 2 |
| 2 | ab | 1 |
| 3 | qqqq | 4 |
| 4 | xyzzyxy | 1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
