eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Суффиксный массив

Суффиксный массив

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Дана строка, требуется построить суффиксный массив для этой строки. Суффиксный массив - лексикографически отсортированный массив всех суффиксов строки. Каждый суффикс задается целым числом — позицией начала.

Строка s лексикографически меньше строки t, если существует такое i, что s[i] < t[i] и s[j] = t[j] для всех j < i. Или, если такого i не существует и строка s короче строки t.

Здесь s[i] - код i-го символа строки s.

Входные данные

Одна строка - английский литературный текст. Длина текста не превосходит 10^5. Коды всех символов в тексте от 32 до 127.

Выходные данные

Выведите n чисел - суффиксный массив данной строки.

Пример

Входные данные #1
99 bottles of beer.
Выходные данные #1
14 3 11 19 2 1 15 4 16 17 9 13 8 12 5 18 10 7 6
Источник 2012 Харьков, Зимняя школа, День Сергея Копеловича, Задача N