Циклические сдвиги
(Время: 5 сек. Память: 16 Мб Сложность: 76%)
Циклическим сдвигом строки s называется строка sk+1sk+2…sns1s2…sk для некоторого k (0 ≤ k < n), где n – длина строки s.
Для заданной строки требуется построить все ее циклические сдвиги, упорядочить их лексикографически, выписать последний столбец и найти в данном списке позицию исходной строки.
Входные данные
В единственной строке входного файла INPUT.TXT записана строка, состоящая из символов с кодами ASCII от 33 до 127. Длина строки не превышает 105.
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите номер позиции исходного слова в отсортированном списке циклических сдвигов. Если таких позиций несколько, то следует вывести позицию с наименьшим номером. Во второй строке выведите последний столбец таблицы циклических сдвигов.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | abraka | 2 karaab |
Пояснение к примеру
Первоначально выпишем все 6 циклических сдвигов строки «abraka» и упорядочим получившийся список лексикографически:
Исходный список | Упорядоченный список |
abraka
brakaa
rakaab
akaabr
kaabra
aabrak | aabrak
abraka
akaabr
brakaa
kaabra
rakaab |
Теперь видно, что в упорядоченным списке исходное слово находится на 2-й позиции, а последний столбец представляет собой строку «karaab».
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|