Задание 1. Алгоритм Лемпеля-Зива
Как Вам известно, подавляющее большинство современных форматов записи данных содержат их в виде, удобном для быстрого манипулирования, для удобного прочтения пользователями. При этом данные занимают объем больший, чем это действительно требуется для их хранения. Алгоритмы, которые устраняют избыточность записи данных, называются алгоритмами сжатия данных, или алгоритмами архивации.
Одним из алгоритмов сжатия данных без потерь является алгоритм Лемпеля-Зива – LZ77, названный так по году своего опубликования, предельно прост. Он формулируется следующим образом : "если в прошедшем ранее выходном потоке уже встречалась подобная последовательность байт, причем запись о ее длине и смещении от текущей позиции короче чем сама эта последовательность, то в выходной файл записывается ссылка (смещение, длина), а не сама последовательность". Длина может быть больше модуля смещения.
Требуется написать программу, которая из последовательности символов, архивированной с помощью алгоритма Лемпеля-Зива, формирует полную строку символов.
Исходные данные
Данные вводятся со стандартного устройства ввода. Последовательность, упакованная по приведённому выше алгоритму, имеет формат (n, m), где n – смещение относительно текущего символа, m – количество извлекаемых символов.
Выходные данные
Данные выводятся на стандартное устройство вывода. Пробелы в конце строки не допускаются.
Пример исходных данных:
бал с (-6,3)(-2,3)йкой
Пример выходных данных:
бал с балалайкой
