Узор на барабане добулбаш
Отправить решение
Решать в редакторе
Сложность:
80%
Очки:
100 (частичный балл)
Ограничение по времени:
2.0s
Ограничение по памяти:
256M
Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch
Барабанщик расписывает обод барабана добулбаш узором из n значков, значки обозначены строчными латинскими буквами. Обод круглый, поэтому узор можно начинать читать с любого места: прочитав с позиции i, мы получаем циклический сдвиг s[i] s[i+1] … s[n] s[1] … s[i−1].
Для данной строки s найдите:
- наименьшую позицию
i, с которой начинается лексикографически наименьший циклический сдвиг; - количество различных циклических сдвигов;
- количество слов в разложении Линдона строки
s: строку единственным образом можно разрезать на словаw₁ ≥ w₂ ≥ … ≥ w_k(сравнение лексикографическое), каждое из которых строго меньше любого своего собственного циклического сдвига (такие слова называют словами Линдона). Нужно найтиk.
Входные данные
В единственной строке — строка s (1 ≤ |s| ≤ 10⁶) из строчных латинских букв.
Выходные данные
Выведите три числа через пробел.
Пример 1
Вход:
cabcab
Выход:
2 3 3
Пояснение
Для cabcab наименьший сдвиг abcabc начинается с позиции 2 (и с позиции 5, но нужна наименьшая); различных сдвигов три: cabcab, abcabc, bcabca. Разложение Линдона: c · abc · ab, три слова.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов |s| ≤ 300.
Подсказка
Алгоритм Дюваля строит разложение Линдона за линейное время.
Комментарии