Форум сайта python.su
Задача звучит следующим образом:
Преобразование Барроуза-Уилера выполняется в три этапа:
1. Составляется таблица всех циклических сдвигов входной строки.
2. Производится лексикографическая (в алфавитном порядке) сортировка строк таблицы. Лексикографическая сортировка происходит в соответствии с кодировкой Unicode.
3. В качестве выходной строки выбирается последний столбец таблицы преобразования и номер строки, совпадающей с исходной.
Напишите программу, которая делает обратное преобразование Алгоритма Барроуза-Уилера. Алгоритм заключается в разбиении входной строки (уже преобразованной алгоритмом) на последовательность символов, которые записываюся в столбик (добавление 1). Образованные строки лексикографически (unicod) сортируются (сортировка 1), а после к полученному добавляют слева символы из добавления 1 (добавление 2). Снова сортируют, продолжая таким образом, пока количество символов в полученных строках не станет равным количеству символов во входной строке. При любом добавлении добавляем символы из первого столбца. В конце образуется столбец, где искомая строка это строка c символом конца строки ‘|’.
**Входные данные:** строка, зашифрованная алгоритмом Барроуза-Уилера, длиной до 100 символов
**Пример входных данных:** |_deipPPier
**Выходные данные:** расшифрованная строка
**Пример выходных данных:** Pied_Piper|
С приведенным выше примером у меня все работает. Но если входная строка “BNNZAA|Aier”, то выводит “|ZBANANAer|”, что неправильно, потому что пропала “i”. Путем вывода промежуточных результатов и решения вручную я поняла, что это происходит из-за того, что порядок буквы “i” в столбце дополнения совпадает с её порядком в отсортированном столбце. То есть одна из строк получившейся матрицы “iiiiiiiiiii”, что выбрасывает её.
Подскажите, пожалуйста, как это можно пофиксить. У меня в коде может ошибка или это алгоритм нуждается в доработке?
Прямой код (вроде работает правильно):
import sys def transformation(input): if len(input) == 0: return None cycle_list = sorted([input[i+1:]+input[:i+1] for i in range(len(input))]) output = "" for s in cycle_list: output += s[len(s)-1] return output if __name__ == '__main__': for line in sys.stdin: print(transformation(line[:-1]))
import sys def re_transformation(input): if len(input) == 0: return None re_cycle_list = ["" for s in input] while len(re_cycle_list[0]) < len(input): re_cycle_list = sorted([input[i]+re_cycle_list[i] for i in range(len(input))]) for s in re_cycle_list: if s[len(s)-1] == '|': return s if __name__ == '__main__': for line in sys.stdin: print(re_transformation(line[:-1]))
Отредактировано wolfram18 (Март 7, 2024 12:16:09)
Офлайн