1302
правки
Изменения
Нет описания правки
==Наивный алгоритм==
===Описание===
Если отсортировать символы последнего столбца матрицы перестановок - — а перед началом обратного преобразования нам известен только он - — то мы получим первый столбец данной матрицы,так как строки матрицы были отсортированы в лексикографическом порядке.
Известно, что символы последнего столбца предшествуют символам первого, находящимся в той же строке, поскольку использовался циклический сдвиг. Таким образом, мы имеем уже список пар, состоящих из символа последнего столбца и следующего за ним символа первого столбца. После сортировки этих пар мы обретаем знание о двух первых столбцах матрицы. И так далее, пока мы не получим всю матрицу перестановок, на каждом шаге новый префикс получается в результате конкатенации последнего символа и соответствующего ему префикса. В результате получаем матрицу, содержащую все циклические сдвиги, откуда выписываем строку с заданным номером. Рассмотрим этот алгоритм на конкретном примере. Пусть дана строка "абракадабра". В результате преобразования получаем набор ("рдакраааабб", 3).
{|
|}
|}
Зная номер исходной строки - — 3, мы воспроизводим входные данные - — "абракадабра".
===Сложность===
Как несложно посчитать сложность данного алгоритма <tex>O(N^3logN) </tex>, также он требует <tex>O(N^2)</tex> памяти.
|}
===Сложность===
Данный алгоритм работает за <tex>O(NlogN)</tex> действий и требует <tex>O(N)</tex> памяти. Однако, если размер алфавита не очень большой, то для выяснения 1ого столбца матрицы можно использовать сортировку подсчетом, в этом случае алгоритм работает за <tex>O(N+M)</tex> действий и требует <tex>O(N+M)</tex> памяти, где <tex>M</tex> - — размер алфавита.
===Псевдокод===
Пусть N - — количество символов во входной строке, M - — количество символов в алфавите, k - — номер исходной строки в матрице перестановок, s - — входящая строка, count - — массив для сортировки подсчетом, t - — вектор обратного преобразования.
//считаем частоты символов
