Минимальный циклический сдвиг
(Время: 1 сек. Память: 16 Мб Сложность: 15%)
Циклическим сдвигом строки s называется строка sk+1sk+2…sns1s2…sk для некоторого k (0 ≤ k < n), где n – длина строки s.
Для заданной строки требуется определить ее лексикографически минимальный циклический сдвиг, т.е. необходимо найти среди всех возможных циклических сдвигов строки тот, который идет первым в алфавитном порядке.
Входные данные
В единственной строке входного файла INPUT.TXT записана строка, состоящая из заглавных букв английского алфавита. Длина строки от 1 до 1000 символов.
Выходные данные
В выходной файл OUTPUT.TXT выведите одну строку – лексикографически минимальный циклический сдвиг исходной строки.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | CAB | ABC |
2 | ABCAAAC | AAACABC |
Пояснение
Чтобы лексикографически сравнить две различные строки одинаковой длины, нужно найти в них первое несовпадение символов при просмотре слева направо. Меньшей будет та строка, у которой несовпадающий символ идет раньше в английском алфавите.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|