Изменения
→Суть алгоритма
===Суть алгоритма===
Если отсортировать символы последнего столбца матрицы перестановок — а перед началом обратного преобразования нам известен только он — то мы получим первый столбец данной матрицы, так как строки матрицы были отсортированы в лексикографическом порядке.
Известно, что символы последнего столбца предшествуют символам первого, находящимся в той же строке, поскольку использовался циклический сдвиг. Таким образом, мы имеем уже список пар, состоящих из символа последнего столбца и следующего за ним символа первого столбца. После сортировки этих пар мы обретаем знание получаем информацию о двух первых столбцах матрицы. И так далее, пока мы не получим всю матрицу перестановок, на каждом шаге новый префикс получается в результате конкатенации последнего символа и соответствующего ему префикса. В результате получаем матрицу, содержащую все циклические сдвиги, откуда выписываем строку с заданным номером. Рассмотрим этот алгоритм на конкретном примере. Пусть дана строка "абракадабра". В результате преобразования получаем набор ("рдакраааабб", 3).
{|
|
