Школа программиста
Резервная копия - VPS Hoster 

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

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

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Простые задачи
 Алгоритмы на строках
 Полиномиальный хеш
 A. Антипалиндром
 B. Префикс-функция
 C. Z-функция
 D. Поле чудес
 E. Поиск подстроки
 F. Сдвиг текста
 G. Циклическая строка
 H. Суффиксы
 I. Количество различных подстрок
 J. Дендрохронология
 K. Abracadabra
 L. Алгоритм Манакера

Красноярский краевой Дворец пионеров, (c)2006 - 2023, ICQ: 151483, E-mail: admin@acmp.ru



донбасс скю