エントロピー符号 〜 横へな 2013.3.1 の参考問題

問題

16d9d4fbd のような符号がある。これを復号し、復号結果の文字列と復号に利用した符号のビット数をコロンでつなげて出力する。
前述の符号は 30 bit が有効な符号で、復号の結果は ethanol なので、 ethanol:30 のように出力する。
不正な符号だった場合は *invalid* と出力する。

符号の説明

1bit ずつ流れてくる信号を4bitずつ16進数としてまとめたものが入力の符号である。 符号は文字を表すビット列の連なりが続き、その後、終端符号がある。終端符号以降のビット列は無視する。

符号の意味は次表のとおり。

符号 意味
000 文字 t
0010 文字 s
0011 文字 n
0100 文字 i
01010 文字 d
0101101 文字 c
010111 文字 l
0110 文字 o
0111 文字 a
10 文字 e
1100 文字 r
1101 文字 h
111 終端

計算の例

入力は 16d9d4fbd のような文字列で与えられる。
符号の各キャラクタを4bitの16進数とみなし、2進数に変換する。このとき、小さい桁が左になるように 0/1 を並べると
1000 0110 1011 1001 1011 0010 1111 1101 1011
となる。
上の表を見ながら左端から順に対応する文字を探すと

符号 10 000 1101 0111 0011 0110 010111 111 011011
文字 e t h a n o l 終端 未使用
となる。
使用したのは 30 ビット(終端符号含む)なので、 ethanol:30 と出力すればよい。

補足

サンプルデータ

# 入力 期待
0 16d9d4fbd ethanol:30
1 df e:5
2 ad7 c:10
3 870dcb t:6
4 880f63d test:15
5 a57cbe56 cat:17
6 36abef2 roll:23
7 ad576cd8 chant:25
8 3e2a3db4fb9 rails:25
9 51aa3b4c2 eeeteee:18
10 ad5f1a07affe charset:31
11 4ab8a86d7afb0f slideshare:42
12 ac4b0b9faef doctor:30
13 cafebabe nlh:17
14 43e7 sra:15
15 53e7 eera:15
16 86cf tera:16
17 b6cf hon:15
18 0 *invalid*
19 c *invalid*
20 d *invalid*
21 e *invalid*
22 babecafe *invalid*
23 8d *invalid*
24 ad *invalid*
25 af *invalid*
26 ab6e0 *invalid*
27 a4371 *invalid*
28 a4371 *invalid*
29 96e3 *invalid*
30 0dc71 *invalid*
31 2a9f51 *invalid*
32 a43fb2 *invalid*
33 ab6e75 *invalid*
34 a5dcfa *invalid*
35 ca97 *invalid*
36 6822dcb *invalid*

C/C++/Java 用のテストデータ