#include <bits/stdc++.h>
using namespace std;
struct trie
{
char b[50];
int words;
struct trie *edges[30];
};
struct trie *root;
struct trie *initialise(struct trie *node)
{
int i;
node = (struct trie *)malloc(sizeof(struct trie));
node->b[0] = '\0';
node->words = 0;
for(i = 0; i < 30; i++) {
node->edges[i] = NULL;
}
return node;
}
void addword(char s[],struct trie *temp)
{
int i;
int k;
for(i = 0; i < strlen(s);i++) {
k = s[i] - 'a';
if(temp->edges[k] == NULL) {
temp->edges[k] = initialise(temp->edges[k]);
}
temp = temp->edges[k];
}
temp->words = 1;
strcpy(temp->b,s);
}
struct trie *findword(char s[],struct trie *temp)
{
int i;
int k;
for(i = 0; i < strlen(s); i++) {
k = s[i] - 'a';
if(temp->edges[k] == NULL) {
return NULL;
}
temp = temp->edges[k];
}
return temp;
}
int bfs(struct trie *node,char s[])
{
queue<struct trie *> q;
struct trie *temp;
temp = initialise(temp);
int i;
int count;
count = 0;
q.push(node);
while(!q.empty()) {
temp = q.front();
//cout << "hi " << temp->b << endl;
if(temp->words == 1 && strcmp(temp->b,s) != 0) {
printf("%s\n",temp->b);
count++;
}
q.pop();
for(i = 0; i < 26; i++) {
if(temp->edges[i] != NULL) {
q.push(temp->edges[i]);
}
}
}
return count;
}
int main()
{
int i;
char s[50];
char a[50];
int n;
int k;
root = initialise(root);
struct trie *temp;
temp = initialise(temp);
scanf("%d",&n);
for(i = 0; i < n; i++) {
scanf("%s",s);
addword(s,root);
}
int j;
scanf("%d",&k);
for(i = 1; i <= k; i++) {
scanf("%s",a);
printf("Case #%d:\n",i);
temp = findword(a,root);
if(temp == NULL) {
printf("No match.\n");
}
else {
//cout << "bfs " << temp->b << endl;
int count = bfs(temp,a);
if(count == 0) {
printf("No match.\n");
}
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnN0cnVjdCB0cmllCnsKICAgIGNoYXIgYls1MF07CiAgICBpbnQgd29yZHM7CiAgICBzdHJ1Y3QgdHJpZSAqZWRnZXNbMzBdOwp9OwpzdHJ1Y3QgdHJpZSAqcm9vdDsKc3RydWN0IHRyaWUgKmluaXRpYWxpc2Uoc3RydWN0IHRyaWUgKm5vZGUpCnsKICAgIGludCBpOwogICAgbm9kZSA9IChzdHJ1Y3QgdHJpZSAqKW1hbGxvYyhzaXplb2Yoc3RydWN0IHRyaWUpKTsKICAgIG5vZGUtPmJbMF0gPSAnXDAnOwogICAgbm9kZS0+d29yZHMgPSAwOwogICAgZm9yKGkgPSAwOyBpIDwgMzA7IGkrKykgewogICAgICAgIG5vZGUtPmVkZ2VzW2ldID0gTlVMTDsKICAgIH0KCiAgICByZXR1cm4gbm9kZTsKfQp2b2lkIGFkZHdvcmQoY2hhciBzW10sc3RydWN0IHRyaWUgKnRlbXApCnsKICAgIGludCBpOwogICAgaW50IGs7CgoKICAgIGZvcihpID0gMDsgaSA8IHN0cmxlbihzKTtpKyspIHsKICAgICAgICBrID0gc1tpXSAtICdhJzsKICAgICAgICBpZih0ZW1wLT5lZGdlc1trXSA9PSBOVUxMKSB7CiAgICAgICAgICAgIHRlbXAtPmVkZ2VzW2tdID0gaW5pdGlhbGlzZSh0ZW1wLT5lZGdlc1trXSk7CiAgICAgICAgfQogICAgICAgIHRlbXAgPSB0ZW1wLT5lZGdlc1trXTsKICAgIH0KICAgIHRlbXAtPndvcmRzID0gMTsKICAgIHN0cmNweSh0ZW1wLT5iLHMpOwp9CnN0cnVjdCB0cmllICpmaW5kd29yZChjaGFyIHNbXSxzdHJ1Y3QgdHJpZSAqdGVtcCkKewogICAgaW50IGk7CiAgICBpbnQgazsKCiAgICBmb3IoaSA9IDA7IGkgPCBzdHJsZW4ocyk7IGkrKykgewogICAgICAgIGsgPSBzW2ldIC0gJ2EnOwogICAgICAgIGlmKHRlbXAtPmVkZ2VzW2tdID09IE5VTEwpIHsKICAgICAgICAgICAgcmV0dXJuIE5VTEw7CiAgICAgICAgfQogICAgICAgIHRlbXAgPSB0ZW1wLT5lZGdlc1trXTsKICAgIH0KCiAgICByZXR1cm4gdGVtcDsKfQoKaW50IGJmcyhzdHJ1Y3QgdHJpZSAqbm9kZSxjaGFyIHNbXSkKewogICAgcXVldWU8c3RydWN0IHRyaWUgKj4gcTsKICAgIHN0cnVjdCB0cmllICp0ZW1wOwogICAgdGVtcCA9IGluaXRpYWxpc2UodGVtcCk7CiAgICBpbnQgaTsKICAgIGludCBjb3VudDsKICAgIGNvdW50ID0gMDsKCiAgICBxLnB1c2gobm9kZSk7CgogICAgd2hpbGUoIXEuZW1wdHkoKSkgewogICAgICAgIHRlbXAgPSBxLmZyb250KCk7CiAgICAgICAgLy9jb3V0IDw8ICJoaSAiIDw8IHRlbXAtPmIgPDwgZW5kbDsKICAgICAgICBpZih0ZW1wLT53b3JkcyA9PSAxICYmIHN0cmNtcCh0ZW1wLT5iLHMpICE9IDApIHsKICAgICAgICAgICAgcHJpbnRmKCIlc1xuIix0ZW1wLT5iKTsKICAgICAgICAgICAgY291bnQrKzsKICAgICAgICB9CiAgICAgICAgcS5wb3AoKTsKCiAgICAgICAgZm9yKGkgPSAwOyBpIDwgMjY7IGkrKykgewogICAgICAgICAgICBpZih0ZW1wLT5lZGdlc1tpXSAhPSBOVUxMKSB7CiAgICAgICAgICAgICAgICBxLnB1c2godGVtcC0+ZWRnZXNbaV0pOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKICAgIHJldHVybiBjb3VudDsKCn0KaW50IG1haW4oKQp7CiAgIGludCBpOwogICAgY2hhciBzWzUwXTsKICAgIGNoYXIgYVs1MF07CiAgIGludCBuOwogICBpbnQgazsKICAgcm9vdCA9IGluaXRpYWxpc2Uocm9vdCk7CiAgIHN0cnVjdCB0cmllICp0ZW1wOwogICB0ZW1wID0gaW5pdGlhbGlzZSh0ZW1wKTsKICAgIAogICBzY2FuZigiJWQiLCZuKTsKICAgZm9yKGkgPSAwOyBpIDwgbjsgaSsrKSB7CiAgICAgICAgc2NhbmYoIiVzIixzKTsKICAgICAgICBhZGR3b3JkKHMscm9vdCk7CiAgIH0KICAgaW50IGo7CgogICBzY2FuZigiJWQiLCZrKTsKICAgZm9yKGkgPSAxOyBpIDw9IGs7IGkrKykgewogICAgICAgIHNjYW5mKCIlcyIsYSk7CiAgICAgICAgcHJpbnRmKCJDYXNlICMlZDpcbiIsaSk7CiAgICAgICAgdGVtcCA9IGZpbmR3b3JkKGEscm9vdCk7CiAgICAgICAgaWYodGVtcCA9PSBOVUxMKSB7CiAgICAgICAgICAgIHByaW50ZigiTm8gbWF0Y2guXG4iKTsKICAgICAgICB9CiAgICAgICAgZWxzZSB7CiAgICAgICAgICAgIC8vY291dCA8PCAiYmZzICIgPDwgdGVtcC0+YiA8PCBlbmRsOwogICAgICAgICAgIGludCBjb3VudCA9ICBiZnModGVtcCxhKTsKICAgICAgICAgICBpZihjb3VudCA9PSAwKSB7CiAgICAgICAgICAgICAgIHByaW50ZigiTm8gbWF0Y2guXG4iKTsKICAgICAgICAgICB9CgogICAgICAgIH0KCiAgIH0KCiAgIHJldHVybiAwOwoKCgoKCn0K