这题记得曾经是我们周赛的题，然后用的是map，也暴过了。
由于这两天要给大一的讲字典树。所以练练几道的代码，以防给大一搞晕了……
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define INF 510010
#define maxn 400010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int ch[maxn][27]; //节点编号
int sz; //字典树的节点个数
int val[maxn]; //节点的值。为1说明新增一个字符串
char str[maxn][11];
void init() //初始化
{
sz=1;
memset(ch,0,sizeof(ch));
memset(val,0,sizeof(val));
}
void insert(char *s,char *ss)
{
int u=0,i,c,l=strlen(ss);
for(i=0; i<l; i++)
{
c=ss[i]-'a';
if(!ch[u][c]) ch[u][c]=sz++;
u=ch[u][c];
}
val[u]=1;
strcpy(str[u],s);
}
void query(char *s)
{
int u=0,i,c,l=strlen(s),flag=1;
for(i=0; i<l; i++)
{
c=s[i]-'a';
if(!ch[u][c]) {flag=0;break;}
u=ch[u][c];
}
if(val[u]&&flag) printf("%s
",str[u]);
else puts("eh");
}
int main()
{
char s[22],s1[12],s2[12];
init();
while(gets(s),s[0]!=' ')
{
int i,len=strlen(s),j=0,k=0,flag=1;
for(i=0;i<len;i++)
{
if(s[i]!=' '&&flag) s1[j++]=s[i];
else if(s[i]!=' '&&!flag) s2[k++]=s[i];
else flag=0;
}
s1[j]=' ';s2[k]=' ';
insert(s1,s2);
}
while(gets(s)) query(s);
return 0;
}