1 /*
  2 模板题
  3 
  4 */
  5 #include<iostream>
  6 #include<stdio.h>
  7 #include<cstring>
  8 #include<cstdlib>
  9 using namespace std;
 10 
 11 struct Tril
 12 {
 13     char a[20];
 14     struct Tril *next[26];
 15 };
 16 Tril *root;
 17 void mem(Tril *p)
 18 {
 19     int i;
 20     for(i=0;i<26;i++) p->next[i]=NULL;
 21     p->a[0]=‘\0‘;
 22 }
 23 
 24 void insert_Tril(char *s1,char *s2)
 25 {
 26     int i,k,ans;
 27     struct Tril *p=root,*q;
 28     k=strlen(s2);
 29     for(i=0;i<k;i++)
 30     {
 31         ans=s2[i]-‘a‘;
 32         if( p->next[ans]==NULL )
 33         {
 34             q=(struct Tril*)malloc(sizeof(struct Tril));
 35             mem(q);
 36             p->next[ans]=q;
 37             p=q;
 38         }
 39         else
 40         {
 41             p=p->next[ans];
 42         }
 43     }
 44     strcpy(p->a,s1);
 45 }
 46 void found_Tril(char *s1)
 47 {
 48     int i,k,ans;
 49     struct Tril *p=root;
 50     bool flag=false;
 51     k=strlen(s1);
 52     for(i=0;i<k;i++)
 53     {
 54         ans=s1[i]-‘a‘;
 55         if(p->next[ans]==NULL)
 56         {
 57             flag=true;
 58             break;
 59         }
 60         else p=p->next[ans];
 61     }
 62     if(flag==true || strlen(p->a)==0)
 63         printf("%s",s1);
 64     else printf("%s",p->a);
 65 }
 66 int main()
 67 {
 68     int i,k;
 69     char s1[3014],s2[3014];
 70     root=(struct Tril*)malloc(sizeof(struct Tril));
 71     mem(root);
 72     scanf("%s",s1);
 73     while(scanf("%s",s1))
 74     {
 75         if( strcmp(s1,"END")==0)break;
 76         scanf("%s",s2);
 77         insert_Tril(s1,s2);
 78     }
 79     scanf("%s",s1);
 80     getchar();
 81     while(gets(s1))
 82     {
 83         if( strcmp(s1,"END")==0)break;
 84         i=0;
 85         while(s1[i]!=‘\0‘)
 86         {
 87             if( s1[i]>‘z‘||s1[i]<‘a‘)
 88             {
 89                 printf("%c",s1[i]);
 90                 i++;
 91             }
 92             else
 93             {
 94                 k=0;
 95                 while(s1[i]<=‘z‘&&s1[i]>=‘a‘ &&s1[i]!=‘\0‘)
 96                 {
 97                     s2[k]=s1[i];
 98                     i++;
 99                     k++;
100                 }
101                 s2[k]=‘\0‘;
102                 found_Tril(s2);
103             }
104         }
105         printf("\n");
106     }
107     return 0;
108 }