d72b5571 |
1 | #include <stdio.h> |
2 | #include <stdlib.h> |
3 | |
4 | struct node |
5 | { |
6 | int l, r, c; |
7 | }; |
8 | |
9 | struct node tree[512]; |
10 | int newnode = 1; |
11 | |
12 | int getbits(int numbits) |
13 | { |
14 | static int cb = 8, c; |
15 | int ret; |
16 | |
17 | if(numbits < 0) |
18 | { |
19 | cb = 8; |
20 | return(0); |
21 | } |
22 | ret = 0; |
23 | for(; numbits > 0; numbits--) |
24 | { |
25 | if(cb >= 8) |
26 | { |
27 | c = getc(stdin); |
28 | cb = 0; |
29 | } |
30 | ret <<= 1; |
31 | if(c & (1 << (cb++))) |
32 | ret |= 1; |
33 | } |
34 | return(ret); |
35 | } |
36 | |
37 | int main(int argc, char **argv) { |
38 | int i, o; |
39 | int n; |
40 | int size, ts, c; |
41 | int chars[256], lens[256]; |
42 | |
43 | for(i = 0; i < 512; i++) |
44 | tree[i].l = tree[i].r = tree[i].c = -1; |
45 | if((getc(stdin) != 'H') || |
46 | (getc(stdin) != 'E') || |
47 | (getc(stdin) != '3') || |
48 | (getc(stdin) != 13)) { |
49 | fprintf(stderr, "not a HE3 file\n"); |
50 | exit(1); |
51 | } |
52 | getc(stdin); |
53 | fread(&size, 4, 1, stdin); |
54 | ts = 0; |
55 | fread(&ts, 2, 1, stdin); |
56 | for(i = 0; i < ts; i++) { |
57 | chars[i] = getc(stdin); |
58 | lens[i] = getc(stdin); |
59 | } |
60 | for(i = 0; i < ts; i++) { |
61 | n = 0; |
62 | for(o = 0; o < lens[i]; o++) { |
63 | if(getbits(1)) { |
64 | if(tree[n].r < 0) |
65 | n = tree[n].r = newnode++; |
66 | else |
67 | n = tree[n].r; |
68 | } else { |
69 | if(tree[n].l < 0) |
70 | n = tree[n].l = newnode++; |
71 | else |
72 | n = tree[n].l; |
73 | } |
74 | } |
75 | if(tree[n].c >= 0) { |
76 | fprintf(stderr, "double-used node: \"%c\"\n", chars[i]); |
77 | exit(1); |
78 | } |
79 | tree[n].c = chars[i]; |
80 | } |
81 | getbits(-1); |
82 | n = 0; |
83 | for(i = 0; i < size;) { |
84 | if(getbits(1)) |
85 | n = tree[n].r; |
86 | else |
87 | n = tree[n].l; |
88 | if(n < 0) { |
89 | fprintf(stderr, "invalid path"); |
90 | exit(1); |
91 | } |
92 | if(tree[n].c >= 0) { |
93 | putc(tree[n].c, stdout); |
94 | n = 0; |
95 | i++; |
96 | } |
97 | } |
98 | return(0); |
99 | } |