poj 1051 P,MTHBGWB

P,MTHBGWB

Description

Morse code represents characters as variable length sequences of dots and dashes. In practice, characters in a message are delimited by short pauses. The following table shows the Morse code sequences:

Note that four dot-dash combinations are unassigned. For the purposes of this problem we will assign them as follows (these are not the assignments for actual Morse code):

Thus, the message "ACM_GREATER_NY_REGION" is encoded as:
.- -.-. -- ..-- --. .-. . .- - . .-. ..-- -. -.-- ..-- .-. . --. .. --- -.
M.E. Ohaver proposed an encryption scheme based on mutilating Morse code. Her scheme replaces the pauses between letters, necessary because Morse is a variable-length encoding that is not prefix-free, with a string that identifies the number of dots and dashes in each. For example, consider the message ".--.-.--". Without knowing where the pauses should be, this could be "ACM", "ANK", or several other possibilities. If we add length information, however, ".--.-.--242", then the code is unabiguous.
Ohaver's scheme has three steps, the same for encryption and decryption:
1. Convert the text to Morse code without pauses but with a string of numbers to indicate code lengths
2. Reverse the string of numbers
3. Convert the dots and dashes back into to text using the reversed string of numbers as code lengths
As an example, consider the encrypted message "AKADTOF_IBOETATUK_IJN". Converting to Morse code with a length string yields ".--.-.--..----..-...--..-...---.-.--..--.-..--...----.232313442431121334242". Reversing the numbers and decoding yields the original message "ACM_GREATER_NY_REGION".

Input

This problem requires that you implement Ohaver's encoding algorithm. The input will consist of several messages encoded with Ohaver's algorithm. The first line of the input is an integer n that specifies the number of test cases. The following n lines contain one message per line. Each message will use only the twenty-six capital letters, underscores, commas, periods, and question marks. Messages will not exceed 100 characters in length.

Output

For each message in the input, output the line number starting in column one, a colon, a space, and then the decoded message. The output format must be adhered to precisely.

Sample Input

5
AKADTOF_IBOETATUK_IJN
PUEL
QEWOISE.EIVCAEFNRXTBELYTGD.
?EJHUT.TSMYGW?EJHOT
DSU.XFNCJEVE.OE_UJDXNO_YHU?VIDWDHPDJIKXZT?E

Sample Output

1: ACM_GREATER_NY_REGION
2: PERL
3: QUOTH_THE_RAVEN,_NEVERMORE.
4: TO_BE_OR_NOT_TO_BE?
5: THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG

P,MTHBGWB

描述

莫尔斯电码将字符表示为点和破折号的可变长度序列。实际上，消息中的字符由短停顿分隔。下表显示了摩尔斯电码序列：

请注意，四个点划线组合未分配。出于这个问题的目的，我们将按如下方式分配它们（这些不是实际摩尔斯电码的分配）：

因此，消息“ACM_GREATER_NY_REGION”被编码为：
.- -.-。-- ..-- --. .-. . .- - 。.-. ..- - -。-.-- ..-- .-. . ——。.. --- -。
ME Ohaver 提出了一种基于破坏摩尔斯电码的加密方案。她的方案替换了字母之间的停顿，这是必要的，因为 Morse 是一种不无前缀的可变长度编码，用一个字符串标识每个中的点和破折号的数量。例如，考虑消息“.--.-.--”。在不知道停顿应该在哪里的情况下，这可能是“ACM”、“ANK”或其他几种可能性。然而，如果我们添加长度信息“.--.-.--242”，那么代码是明确的。
Ohaver的方案分为三个步骤，加密和解密相同：
1. 将文本转换为莫尔斯电码，没有停顿，但用一串数字来表示代码长度
2. 将数字字符串反转
3. 将点和破折号转换回文本，使用反转的数字字符串作为代码长度
作为示例，考虑加密消息“AKADTOF_IBOETATUK_IJN”。转换为具有长度字符串的摩尔斯电码会产生“.--.-.--..----..-...--..-...---.-.--..-- .-..--...----.232313442431121334242”。反转数字和解码产生原始消息“ACM_GREATER_NY_REGION”。

输入

这个问题需要你实现 Ohaver 的编码算法。输入将由几条用 Ohaver 算法编码的消息组成。输入的第一行是一个整数 n，它指定了测试用例的数量。以下 n 行每行包含一条消息。每条消息将仅使用 26 个大写字母、下划线、逗号、句点和问号。消息长度不超过 100 个字符。

输出

对于输入中的每条消息，输出从第一列开始的行号、冒号、空格，然后是解码的消息。必须严格遵守输出格式。

样本输入

5
AKADTOF_IBOETATUK_IJN
PUEL
QEWOISE.EIVCAEFNRXTBELYTGD。
?EJHUT.TSMYGW?EJHOT
DSU.XFNCJEVE.OE_UJDXNO_YHU?VIDWDHPDJIKXZT?E

样本输出

1：ACM_GREATER_NY_REGION
2：PERL
3：QUOTH_THE_RAVEN，_NEVERMORE。
4：TO_BE_OR_NOT_TO_BE？
5：THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG

代码：

#include 
#include 
using namespace std;

const int maxn=102;

int N,number[maxn],transnum[26]={2,4,4,3,1,4,3,4,2,4,3,4,2,2,3,4,4,3,3,1,3,4,3,4,4,4};
string st,code,translate[26]={".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};

void init()
{
    number[0]=0;
    code="";
}

string encoder(string st,int *num)
{
    string    ans="";
    int        len=st.length();
    
    for (int i=0;i    {
        num[0]++;
        if (st[i]>='A'&&st[i]<='Z')
        {
            ans+=translate[st[i]-65];
            num[num[0]]=transnum[st[i]-65];
            continue;
        }
        switch (st[i])
        {
            case '_'    :ans+="..--"; break;
            case '?'    :ans+="----"; break;
            case ','    :ans+=".-.-"; break;
            case '.'    :ans+="---."; break;
        }
        num[num[0]]=4;
    }
    return ans;
}

void decoder(string code,int *num)
{
    string    cut;

    for (int i=num[0];i>=1;i--)
    {
        cut.erase();
        cut.insert(0,code,0,num[i]);
        code.erase(0,num[i]);
        for (int j=0;j<26;j++)
            if (translate[j]==cut)
                cout<        if (cut=="..--")
            cout<<"_";
        if (cut=="----")
            cout<<"?";
        if (cut==".-.-")
            cout<<",";
        if (cut=="---.")
            cout<<".";
    }
}

int main()
{
    cin>>N;
    getchar();
    for (int i=1;i<=N;i++)
    {
        init();
        getline(cin,st);
        code=encoder(st,number);
        printf("%d: ",i);
        decoder(code,number);
        cout<    }
    return 0;
}