Матч 308, Декодирование Хаффмана (HuffmanDecoding)

Дивизион 2, Уровень 2

При кодировании методом Хаффмана каждая буква кодируется строкой, состоящей из 0 и 1. При этом никакая строка не является префиксом другой. Такое свойство кодов Хаффмана дает возможность однозначного декодирования.

В массиве dictionary содержатся коды Хаффмана для букв: строка dictionary [i] содержит код i – ой заглавной буквы. Необходимо декодировать строку archive, используя массив кодов dictionary.

Класс: HuffmanDecoding

Метод: string decode(string archive, vector<string> dictionary)

Ограничения: archive содержит от 1 до 50 символов ‘0’ и ‘1’, dictionary содержит от 1 до 26 строк, каждая строка dictionary[i] содержит только символы ‘0’ и ‘1’.

Вход. Закодированная строка archive и набор строк dictionary, где dictionary [i] содержит код i – ой заглавной буквы.

Выход. Декодированная строка.

Пример входа

archive	dictionary
“101101”	{“00”,“10”,“01”,“11”}
“0001001100100111001”	{“1”, “0”}
“111011011000100110”	{“010”,“00”,“0110”,“0111”,“11”,“100”,“101”}

Пример выхода

“BDC”

“BBBABBAABBABBAAABBA”

“EGGFAC”

РЕШЕНИЕ

обработка строк

Строки из массива dictionary вместе буквами, которые они кодируют, храним в отображении map<string, char> m. Если буква a кодируется строкой s, то m[s] = a. Просматриваем строку archive сначала до конца и для каждого префикса s, являющийся кодом из dictionary, находим соответствующую букву m[s]. Эту букву дописываем в результирующую строку res.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <map>

#include <string>

using namespace std;

class HuffmanDecoding

{

public:

string decode(string archive, vector <string> dictionary)

{

int i, ptr;

map<string,char> m;

string s,res="";

for(ptr = i = 0; i < dictionary.size(); i++) m[dictionary[i]] = 'A' + i;

while(ptr < archive.size())

{

s = ""; while(!m[s]) s = s + archive[ptr++];

res += m[s];

}

return res;

}

};