2011年10月29日 星期六

213 - Message Decoding


有一種加密演算法會將密文編碼成兩個部份,第一個部份稱為檔頭(header),為一列有多個字元,第二部份為某種形式的資訊,用來做為解碼之用,本題請你對資訊做解碼。

此加密演算法的核心觀念是由一組以0或1所組成的鍵值(key)而來:
0, 00, 01, 10, 000, 001, 010, 011, 100, 101, 110, 0000, 0001, ..., 1101, 1110, 00000, ...

此序列中的第一個鍵值長度為1,接下來長度為2的鍵值有三個,再接下來長度為3的鍵值有七個,長度為4的鍵值共有15個。相同長度的鍵值依序由二進制的0開始每個遞增1而來,但不包含所有位數皆為1的情況。

這些鍵值依序對應到檔頭的每個字元,即鍵值"0"對應到檔頭的第一個字元,"00"對應到第二個字元,第 k 個鍵值對應到第 k 個字元。例如若檔頭如下:

AB#TANCnrtXc
則0對應到A,00對應到B,01 = #,10 = T,000 = A, ..., 110 = X,0000 = c。

被編碼的訊息僅包含字元'0'與'1'及換行字元,換行字元可被忽略。訊息可被區分為許多區段,每一區段的頭三個位數以二進制表示接來下該區段鍵值的長度,例如若一區段的頭三個位數為010,表示該區段接下來的每一個鍵值長度皆為2(00, 01, 10),該區段的最後以連續多個1表示結束,其連續多個1的個數與該區域的鍵值長度相同,所以鍵值長度為2的區段是以11做結尾。整個編碼訊息是以000 表示結束(即為區段的鍵值長度為0時)。將每個鍵值從檔頭資訊中做一對一的對應之後可解碼得到原文。

Input

輸入會有多組測試資料,每組資料會有一列檔頭及一段加密密文,密文可能會分成許多列。檔頭的長度一定不會大於所有不同鍵值的個數(而最大鍵值長度被限制在二進制的111)。若檔頭內有重複出現的字元,表示有不同的鍵值會對應到相同的字元。密文僅包含'0'或'1'字元,其格式如上所述。

換行字元可能出現在密文中的任何地方,你不應該視換行字元為密文的一部份。

Output

請對每組測試資料輸出一列,表示解密後的訊息,每列之間不能有空行。

Sample input

TNM AEIOU
0010101100011
1010001001110110011
11000
$#**\
0100000101101100011100101000

Sample output

TAN ME
##*\$


原文出處

沒有留言:

張貼留言