2026-11-13
decode.cpp
std::string decode(const std::map<std::string, char>& codes, const std::string& bits) {
}
codes は、'0' と '1' からなる符号から1文字への表です。符号の長さはそろっていませんが、どの符号も、ほかの符号の先頭部分にはなっていません。符号を並べてつないだビット列 bits を受け取り、元の文字列を返す decode を書いてください。bits は必ず符号の並びに切り分けられ、空なら空文字列を返します。
入力例 1
decode({{"0", 'a'}, {"10", 'b'}, {"11", 'c'}}, "010110")
出力例 1
"abca"
入力例 2
decode({{"0", 'a'}, {"10", 'b'}, {"11", 'c'}}, "")
出力例 2
""
入力例 3
decode({{"00", 'x'}, {"01", 'y'}, {"1", 'z'}}, "1001101")
出力例 3
"zxzzy"
Reference
Reference
std::string decode(const std::map<std::string, char>& codes, const std::string& bits) {
std::string out;
std::string buf;
for (char b : bits) {
buf += b;
if (auto it = codes.find(buf); it != codes.end()) {
out += it->second;
buf.clear();
}
}
return out;
}
符号の長さがそろっていないので、bits を決まった幅で切ることはできません。代わりに先頭から1ビットずつ buf に足し、buf が表のどれかの符号と一致した時点で、その文字を確定して buf を空に戻します。これは参考実装で、唯一の正解ではありません。
一致した時点で確定してよいのは、どの符号もほかの符号の先頭部分になっていないからです。buf が符号 "10" と一致したなら、"10" で始まる長い符号は表に無いので、もっと読み進めて別の符号になる可能性はありません。入力例3では、1 が z、続く 0 はどれとも一致せず、00 で x になり、残りの 1 1 01 が z z y になります。表は const 参照で受けているので、引くには operator[] ではなく find を使います。operator[] は無いキーを挿入する関数で、const の std::map には呼べません。bits が空ならループが回らず、空の out を返します。