Узор на барабане добулбаш


Отправить решение Решать в редакторе

Сложность: 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 найдите:

  1. наименьшую позицию i, с которой начинается лексикографически наименьший циклический сдвиг;
  2. количество различных циклических сдвигов;
  3. количество слов в разложении Линдона строки 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.

Подсказка

Алгоритм Дюваля строит разложение Линдона за линейное время.


Комментарии

Еще нет ни одного комментария.