Задача №114030. Вася и Циклические Сдвиги
Однажды Василий проголодался и пошел на кухню подкрепиться. Но каково было его удивление, когда, открыв холодильник, он обнаружил там не привычные продукты, а строку! Причем не просто строку, а зацикленную, прямо как бублик (ассоциации с едой часто приходят Васе в голову, когда он голоден). Загадочная строка заинтересовала любопытного, но все еще голодного Василия, и он начал ее вертеть в руках. Например, если вертеть строку abacaba , то можно получить следующие строки:
- abacaba
- bacabaa
- acabaab
- cabaaba
- abaabac
- baabaca
- aabacab
И тут Василия осенило: если он сможет посчитать, сколько раз в процессе кручения строки получается лексикографически минимальная строка, то еда магическим образом появится в холодильнике (странные идеи часто приходят Васе в голову, когда он голоден). Помогите Васе, иначе он так и будет сидеть голодным.
Более формально, вам дана строка. Циклическим сдвигом строки s длины n называется строка, полученнная из исходной путем отбрасывания первых 0 ≤ k < n символов и приписывания их в конец. Необходимо посчитать, сколько раз среди всех циклических сдвигов строки встречается лексикографически минимальный циклический сдвиг.
Единственная строка входного файла содержит строку S , найденную Василием. Она непуста, состоит из маленьких латинских букв, и её длина не превосходит 10 000 000.
Выведите единственное число — искомое количество минимальных циклических сдвигов.
В первом примере минимальным циклическим сдвигом является строка aaaa . Во втором примере минимальным циклическим сдвигом является строка aabacab .
Тесты к этой задаче состоят из шести групп.
- Тесты 1-2. Тесты из условия, эта группа оценивается в ноль баллов.
- Тесты 3–9. В тестах этой группы | S | ≤ 100 . Эта группа оценивается в 20 баллов.
- Тесты 10–18. В тестах этой группы | S | ≤ 10 4 . Эта группа оценивается в 20 баллов.
- Тесты 19–27. В тестах этой группы | S | ≤ 10 5 . Эта группа оценивается в 20 баллов.
- В тестах этой группы | S | ≤ 10 6 . Эта группа оценивается в 20 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура.
- В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 20 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы. Тестирование на тестах каждой группы производится только в случае прохождения всех тестов из всех предыдущих групп.
aaaa
4
abacaba
1