Распаковать LZW
Старый формат хранит текст номерами фраз LZW. Упаковщик начинал со словаря из 256 одиночных байтов и шёл по тексту: продлевал текущую фразу, пока она есть в словаре, выдавал номер самой длинной знакомой фразы и добавлял в словарь её же, продлённую на следующий байт. Словарь самой распаковке не передаётся — распаковщик должен выстроить точно такой же, читая номера. Напишите его.
Правила этого упаковщика:
- номера 0–255 — одиночные байты; номер 256 — CLEAR, команда «словарь сброшен»; новые фразы получают номера 257, 258 и так далее;
- в словаре не больше 4096 номеров (0–4095): когда он полон, новые фразы не добавляются, пока не придёт CLEAR;
- после CLEAR словарь снова состоит из одиночных байтов, а следующая новая фраза получит номер 257.
Например, номера 97 98 257 259 258 261 260 распаковываются в abababababababab. Среди тестов — «Война и мир» по-русски и по-английски, геном фага лямбда и файл, который сжимали так, как это делает программа compress: сбрасывая словарь, когда сжатие ухудшается.
Вход
В первой строке число номеров m (1 ≤ m ≤ 300 000). Дальше m номеров через пробелы и переводы строк. Гарантируется, что это вывод упаковщика с описанными правилами.
Выход
Распакованные байты без изменений (они образуют текст в UTF-8).
Примеры
Пример 1
16 84 79 66 69 79 82 78 79 84 257 259 261 266 260 262 264
TOBEORNOTTOBEORTOBEORNOT
Пример 2
7 97 98 257 259 258 261 260
abababababababab
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Распаковщик отстаёт от упаковщика на шаг. Упаковщик добавляет фразу «прошлая + первый байт следующей» в тот момент, когда выдаёт номер прошлой; распаковщик узнаёт этот байт, только прочитав следующий номер. Значит, новую фразу он добавляет, когда прочитал очередной номер: предыдущая распакованная фраза плюс первый байт текущей.
2Подсказка 2
Распакуйте вручную 97 98 257 259 из примера. На номере 259 что-то пойдёт не так. Что именно и чему этот номер может быть равен?
3Идея
Если номер ещё не в словаре, это ровно тот номер, который упаковщик создал на предыдущем шаге и тут же использовал. Он равен «предыдущая фраза + её же первый байт»: по построению он начинается с предыдущей фразы, а его последний байт — первый байт его самого, то есть первый байт предыдущей. Так бывает на строках вида KwKwK, где K — байт, а w — строка: «abababa», «aaaa».
4Разбор
Словарь — список фраз. Для каждого номера: CLEAR — обрезать список до 257 элементов и забыть предыдущую фразу; известный номер — взять фразу; неизвестный — предыдущая плюс её первый байт. Выдать фразу и, если предыдущая есть и в словаре меньше 4096 номеров, добавить «предыдущая + первый байт текущей». Это lzw_decode из листинга статьи.
В шестом тесте, на пятидесяти тысячах «a», особый случай срабатывает на каждом номере, пока словарь не заполнится: фразы «a», «aa», «aaa»… упаковщик создаёт и сразу использует.
4+Решение
5Сложность
O(длины результата): каждая фраза копируется в выход один раз, а новая фраза — копия предыдущей плюс байт; если хранить фразы ссылкой на префикс, то и память O(m).
6Типичные ошибки
- Нет особого случая. Распаковщик падает на первом номере, которого ещё нет в словаре, — уже во втором примере.
- Словарь не замирает. Если добавлять фразы и после 4096 номеров, номера расходятся с упаковщиком, и всё, что идёт дальше, распаковывается в мусор.
- После CLEAR. Первый номер после сброса — одиночный байт, и новую фразу на нём добавлять нельзя: предыдущей фразы ещё нет.