原題及翻譯

Some message encoding schemes require that an encoded message be sent in two parts.
某些消息編碼方案要求將編碼的消息分為兩部分發送。
The first part, called the header, contains the characters of the message.
第一部分稱為標題，包含消息的字符。
The second part contains a pattern that represents the message.
第二部分包含表示消息的模式。
You must write a program that can decode messages under such a scheme.
您必須編寫一個程序，在這種方案下可以解碼消息。
The heart of the encoding scheme for your program is a sequence of “key” strings of 0’s and 1’s as follows:
程序編碼方案的核心是一系列0和1的“鍵”字符串，如下所示：
0, 00, 01, 10, 000, 001, 010, 011, 100, 101, 110, 0000, 0001, . . . , 1011, 1110, 00000, . . .
The first key in the sequence is of length 1, the next 3 are of length 2, the next 7 of length 3, the next 15 of length 4, etc.
序列中的第一個鍵為長度1，下一個3為長度2，下一個7為長度3，下一個15為長度4等。
If two adjacent keys have the same length, the second can be obtained from the first by adding 1 (base 2).
如果兩個相鄰鍵的長度相同，則可以通過添加1（基2）從第一個鍵獲取第二個鍵。
Notice that there are no keys in the sequence that consist only of 1’s.
注意，序列中沒有只包含1的鍵。
The keys are mapped to the characters in the header in order.
鍵按順序映射到頭中的字符。
That is, the first key (0) is mapped to the first character in the header, the second key (00) to the second character in the header, the kth key is mapped to the kth character in the header.
也就是說，第一個鍵（0）映射到頭中的第一個字符，第二個鍵（00）映射到頭中的第二個字符，第k個鍵映射到頭中的第k個字符。
For example, suppose the header is:
例如，假設頭是：
AB#TANCnrtXc
Then 0 is mapped to A, 00 to B, 01 to #, 10 to T, 000 to A, …, 110 to X, and 0000 to c.
然后0映射到A，00到B，01到#，10到T，000到A，…，110到X，0000到c。
The encoded message contains only 0’s and 1’s and possibly carriage returns, which are to be ignored.
編碼的消息只包含0和1，并且可能包含回車，這將被忽略。
The message is divided into segments.
消息分為段。
The first 3 digits of a segment give the binary representation of the length of the keys in the segment.
段的前3位數字給出段中鍵的長度的二進制表示。
For example, if the first 3 digits are 010, then the remainder of the segment consists of keys of length 2 (00, 01, or 10).
例如，如果前3位是010，則段的其余部分由長度為2（00、01或10）的鍵組成。
The end of the segment is a string of 1’s which is the same length as the length of the keys in the segment.
段的末尾是一個1的字符串，其長度與段中鍵的長度相同。
So a segment of keys of length 2 is terminated by 11.
因此，長度為2的鍵段以11結尾。
The entire encoded message is terminated by 000 (which would signify a segment in which the keys have length 0).
整個編碼的消息以000結尾（這表示密鑰長度為0的段）。
The message is decoded by translating the keys in the segments one-at-a-time into the header characters to which they have been mapped.
通過將段中的鍵一次轉換為它們映射到的頭字符，可以對消息進行解碼。

Input

輸入
The input file contains several data sets.
輸入文件包含多個數據集。
Each data set consists of a header, which is on a single line by itself, and a message, which may extend over several lines.
每個數據集包括一個單獨在一行上的頭和一條可能擴展到多行上的消息。
The length of the header is limited only by the fact that key strings have a maximum length of 7 (111 in binary).
頭的長度僅受以下事實的限制：鍵字符串的最大長度為7（二進制為111）。
If there are multiple copies of a character in a header, then several keys will map to that character.
如果一個標題中有一個字符的多個副本，那么幾個鍵將映射到該字符。
The encoded message contains only 0’s and 1’s, and it is a legitimate encoding according to the described scheme.
編碼的消息只包含0和1，根據所描述的方案，它是合法的編碼。
That is, the message segments begin with the 3-digit length sequence and end with the appropriate sequence of 1’s.
也就是說，消息段以3位長度序列開始，以1的適當序列結束。
The keys in any given segment are all of the same length, and they all correspond to characters in the header.
任何給定段中的鍵都具有相同的長度，并且它們都對應于頭中的字符。
The message is terminated by 000.
消息被000終止。
Carriage returns may appear anywhere within the message part.
回車可以出現在消息部分的任何位置。
They are not to be considered as part of the message.
它們不應被視為消息的一部分。

Output

輸出
For each data set, your program must write its decoded message on a separate line.
對于每個數據集，程序必須將其解碼后的消息寫在單獨的行上。
There should not be blank lines between messages.
消息之間不應該有空行。
Sample input
樣例輸入
TNM AEIOU
0010101100011
1010001001110110011
11000
$#**
0100000101101100011100101000
Sample output
樣例輸出
TAN ME
##*$

思路分析

代碼分析

1.首先是讀取編碼并將編碼存儲的函數。
在使用全局變量中的數組時，應該先把數組清零：

memset(code,0,sizeof(code));

由于編碼頭自身占一行，所以可以用readchar()讀取第一個字符，而用普通的getchar（）讀取剩下的字符，知道換行符為止：

code [1][0]=readchar();

而readchar()是這樣定義的：

int readchar() {//跨行讀字符。for(;;){int ch=getchar();if(ch!='\n'&&ch!='\r') return ch; //一直讀到非換行符為止。//也就是說，當讀到不是換行符的時候，返回ch的內容。} }

可以用codes[len][value]這個二維數組來表示一個編碼，其中len是編碼長度，value是編碼對應的十進制值。二進制中，8位最大整數就是8個1，即2⁸-1,用移位運算符表示就是（1<<8）-1。

int readcodes() {//讀取編碼。memset(code,0,sizeof(code));code [1][0]=readchar();//直接調到下一行開始讀取。如果輸入已經結束，會讀到EOF。for(int len=2;len<=7;len++){for(int i=0;i<(1<<len)-1;i++){int ch=getchar();if(ch==EOF) return 0;if(ch=='\n'||ch=='\r') return 1;code[len][i]=ch;}}return 1; }

2.然后是將二進制轉化為十進制的函數，這里采用的二進制轉十進制是一次添加一位的運算方式，每次乘以2，比如說：101₂=（（1*2）+0）*2+1=5。

int readint(int c) {//讀取c位二進制字符（即0和1），并轉化為十進制整數。int v=0;while(c--) v=v*2+readchar()-'0';return v; }

3.最后就是主函數了，讀入數據，調用函數做處理，輸出結果。
用一個無限循環連續處理數據：

for(;;)

要讀入開頭的三個數字代表小節中每個編碼的長度：

int len=readint(3);

然后再來一個無限循環處理代表編碼長度后邊、結束標志前邊的數字：

for(;;){int v=readint(len);//v是len十進制位的二進制數轉化為十進制數后的數if(v==(1<<len)-1) break;//當小節編碼結尾標志11…1出現時，跳出當前循環putchar(code[len][v]);}}

把這些組合起來就是主函數：

int main() {while(readcodes()){//無法讀取更多編碼頭時時退出。for(;;){int len=readint(3);if(len==0) break;//即結尾標志：000for(;;){int v=readint(len);if(v==(1<<len)-1) break;putchar(code[len][v]);}}putchar('\n');}return 0; }

完整代碼

#include <stdio.h> #include <string.h> int code[8][1<<8]; //1<<8表示2的八次方 int readchar() {//跨行讀字符。for(;;){int ch=getchar();if(ch!='\n'&&ch!='\r') return ch; //一直讀到非換行符為止。//也就是說，當讀到不是換行符的時候，返回ch的內容。} } int readint(int c) {//讀取c位二進制字符（即0和1），并轉化為十進制整數。int v=0;while(c--) v=v*2+readchar()-'0';return v; } int readcodes() {//讀取編碼。memset(code,0,sizeof(code));code [1][0]=readchar();//直接調到下一行開始讀取。如果輸入已經結束，會讀到EOF。for(int len=2;len<=7;len++){for(int i=0;i<(1<<len)-1;i++){int ch=getchar();if(ch==EOF) return 0;if(ch=='\n'||ch=='\r') return 1;code[len][i]=ch;}}return 1; } int main() {while(readcodes()){//無法讀取更多編碼頭時時退出。for(;;){int len=readint(3);if(len==0) break;for(;;){int v=readint(len);if(v==(1<<len)-1) break;putchar(code[len][v]);}}putchar('\n');}return 0; }

結語

大道至簡，最簡單的代碼也許難以理解，但這正是算法的美妙之處。

每天磕一道ACM 大年初一打卡

總結

以上是生活随笔為你收集整理的《算法竞赛入门经典》 例题 4-4 信息编码 （Message Decoding,ACM,ICPC World Finals 1991,UVa 213）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。