Problem B
Bad Code
Input: standard input
Output: standard output
 

In his endless attempt to keep his secret documents safe, Bob has designed yet another coding system. In this system, every character is replaced by a unique positive integer value -- which we call the code for a character. However, this system -- as expected -- is not the best in the world. So more than one plain text can result in the same encrypted string. Here are a few more notes:

• The document consists exclusively of lower-case letters.
• The code for a letter is no more than 99.
• The encrypted string does not contain more than 100 characters.
• A code may or may not be preceded by a 0 in the encrypted string (note the 2nd sample test case).

Given the codes for each character and the encrypted string, you have to find all the plain text strings in alphabetical order that produces that encrypted string.

Input

There will be no more than 500 test cases. Each test case starts with an integer N, which gives the number of unique characters in the document. Each of next N lines contains a character in the letter and its code. The last line in the test case gives the encrypted string. The last test case will have N = 0. This last test case need not be processed.

Output

For each test case, print the test case number and the possible plain texts for the given encrypted string. If there is more than 100 possible strings report only the first 100 strings. Print a blank line after the output for each test case.

Sample Input                           Output for Sample Input

5

a 12

b 1

c 2

d 3

e 23

123

2

o 10

x 1

1010101

Case #1

ad

bcd

be

Case #2

ooox

ooxx

oxox

oxxx

xoox

xoxx

xxox

xxxx

Problem setter: Sadrul Habib Chowdhury

Special Thanks: Derek Kisman, EPS

#include <stdio.h>
#include <string.h>
char letter[105], code[105][105];
char str[505], ret[505];
int mapped[105];
int cnt, n;
void dfs(int idx, int depth) {
    if(cnt >= 100)  return;
    if(str[idx] == '\0') {
        ret[depth] = '\0';
        puts(ret);
        cnt++;
        return;
    }
    int i, j, k;
    for(i = 0; i < n; i++) {
        int mm = mapped[i];
        k = idx;
        while(str[k] == '0')    k++;
        for(j = 0; code[mm][j]; j++, k++) {
            if(code[mm][j] != str[k]) {
                break;
            }
        }
        if(code[mm][j] == '\0') {
            ret[depth] = letter[i]+'a';
            dfs(k, depth+1);
        }
        if(cnt >= 100)  return;
    }
}
int main() {
    int cases = 0, i, j;
    while(scanf("%d", &n) == 1 && n) {
        memset(letter, -1, sizeof(letter));
        char s[10];
        for(i = 0; i < n; i++) {
            scanf("%s %s", s, code[i]);
            letter[s[0]-'a'] = i;
        }
        j = 0;
        for(i = 0; i < 26; i++)
            if(letter[i] != -1)
                mapped[j] = letter[i], letter[j] = i, j++;
        scanf("%s", str);
        cnt = 0;
        printf("Case #%d\n", ++cases);
        dfs(0, 0);
        puts("");
    }
    return 0;
}