poj 2503 Babelfish

简单字典树。
 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N = 200000;
 4 int nxt[N][26],word[N];
 5 char eng[N/2+10][11];
 6 bool end[N];
 7 int cnt,cur,p,f;
 8 void insert(char *t, char *s)
 9 {
10     cur = 0;
11     while(*t)
12     {
13         p = *t - 'a';
14         if(!nxt[cur][p])
15         {
16             memset(nxt[cnt],0,sizeof nxt[0]);
17             nxt[cur][p] = cnt++;
18         }
19         cur = nxt[cur][p];
20         t++;
21     }
22     end[cur] = 1;
23     word[cur] = f;
24     strcpy(eng[f++],s);
25 }
26 void query(char *t)
27 {
28     cur = 0;
29     while(*t)
30     {
31         p = *t - 'a';
32         if(!nxt[cur][p])
33         {
34             printf("eh\n");
35             return ;
36         }
37         cur = nxt[cur][p];
38         t++;
39     }
40     if(end[cur])
41         printf("%s\n",eng[word[cur]]);
42 }
43 int main()
44 {
45     char s1[11],s2[11],s[30];
46     cnt = f = 1;
47     memset(nxt[0],0,sizeof nxt[0]);
48     while(gets(s),s[0])
49     {
50         sscanf(s,"%s%s",s1,s2);
51         insert(s2,s1);
52     }
53     while(~scanf("%s",s1))
54         query(s1);
55     return 0;
56 }