1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 #define MAXN 1000100 5 int trie[MAXN][30],tag[MAXN],cnt,sz; 6 char s[MAXN][30],ans[MAXN],tmp[MAXN];  7 void insert(int len){ 8     int x=0; 9     for (int i=0;i<len;i++){10         if (!trie[x][tmp[i]-‘a‘])11             trie[x][tmp[i]-‘a‘]=++sz;12         x=trie[x][tmp[i]-‘a‘];13     }14     tag[x]=cnt;15 }16 int ask(int l,int r){17     int x=0;18     for (int i=l;i<r;i++){19         if (!trie[x][tmp[i]-‘a‘]) return 0;20         x=trie[x][tmp[i]-‘a‘];21     }22     return tag[x];23 }24 int main(){25     cnt=1;sz=0;26     scanf("%s",s[cnt]);27     while (s[cnt][0]!=‘E‘){28         if (s[cnt][0]==‘S‘){29             scanf("%s",s[cnt]);30             continue;31         }32         scanf("%s",tmp);33         int len=strlen(tmp);34         insert(len);35         cnt++;36         scanf("%s",s[cnt]);37     }38     scanf("%s",tmp);39     while (tmp[0]!=‘E‘){40         if (tmp[0]==‘S‘){41             getchar();//这个一定要加上…… 42             gets(tmp);continue;43         }44         int k=0,q=0,p,judge,len=strlen(tmp);45         while (k<len){46             judge=0;p=k;47             while (tmp[k]>=‘a‘&&tmp[k]<=‘z‘){48                 k++;judge=1;49             }50             if (!judge){51                 ans[q]=tmp[k];52                 q++;k++;53                 continue; 54             }55             int pos=ask(p,k);56             if (pos){57                 int lenth=strlen(s[pos]);58                 for (int i=0;i<lenth;i++){59                     ans[q]=s[pos][i];q++;60                 }61             }62             else63                 for (int i=p;i<k;i++){64                     ans[q]=tmp[i];65                     q++;66                 }67         }68         for (int i=0;i<q;i++)69             printf("%c",ans[i]);70         printf("\n");71         gets(tmp);72     }73     return 0;74 }