第一种解法，直接了当的C++ map 水过去

#include<cstdio>
#include<map>
#include<cstring>
using namespace std;
struct word
{
char data[13];
bool operator<(const word& other)const
{
return strcmp(data,other.data)==-1;
}
};
map<word,word> dic;
map<word,word>::iterator it;
word english,foreign;
int main()
{
while(true)
{
char ch=getchar();
if(ch=='\n')
break;
int len=-1;
while(ch!=' ')
{
english.data[++len]=ch;
ch=getchar();
}
english.data[++len]=0;
len=-1;
ch=getchar();
while(ch!='\n')
{
foreign.data[++len]=ch;
ch=getchar();
}             
foreign.data[++len]=0;
dic[foreign]=english;
//         printf("%s %s\n",foreign.data,english.data);
}
while(scanf("%s",foreign.data)!=EOF)
{
it=dic.find(foreign);
if(it==dic.end())
{
printf("eh\n");
}
else
{
printf("%s\n",it->second.data);
}
}
return 0;
}

第二种解法,半hash，主要是排序加二分查找

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct one
{
int i;
unsigned __int64 hash;
bool operator<(const one &other)const
{
return hash<other.hash;
}
};
one hash[100010];
char english[100010][12];
//char foreign[100010][12];
unsigned __int64 hashValue(char *str)
{
int h=0;
while(*str)
h=h*27+(*str++)-'a'+1;
return h; 
}
bool myget(char *str)
{
char ch=getchar();
if(ch==' '||ch=='\n'||ch==EOF)
return false;
while(ch!=' '&&ch!='\n')
{
*str++=ch;
ch=getchar();
}
*str=0;
return true;
}

int main()
{
int i=0;
char foreign[12];
while(myget(&english[i][0]))
{
myget(&foreign[0]);
hash[i].hash=hashValue(foreign);
hash[i].i=i;
++i;
}
sort(hash,hash+i);
char forei[13];
while(myget(forei))
{
one h;
h.hash=hashValue(forei);
int pos=lower_bound(hash,hash+i,h)-hash;
if(pos==i||hash[pos].hash!=h.hash)
printf("eh\n");
else
printf("%s\n",english[hash[pos].i]);
}
return 0;
}

第三种解法， 纯hash

#include<cstdio>
#include<cstring>
int hash[1001][1001];
char english[100010][12];
char foreign[100010][12];
void setHash(int i)
{
     int h=0;
     for(int j=0;foreign[i][j]!=0;++j)
        h=(h*26+(foreign[i][j]-'a'))%1001;
     h=h%1001;
     int j=0;
     while(hash[h][j]!=0)
          ++j;
     hash[h][j]=i;
}
int myHash(char *str)
{
    char *buf=str;
    int h=0;
    for(int j=0;*str!=0;++str)
       h=(h*26+(*str-'a'))%1001;
    h=h%1001;
    int j=0;
    while(hash[h][j]!=0&&strcmp(buf,&foreign[(hash[h][j])][0])!=0)
       ++j;
    return hash[h][j];
}
bool myget(char *str)
{
     char ch=getchar();
     if(ch==' '||ch=='\n'||ch==EOF)
       return false;
     while(ch!=' '&&ch!='\n')
     {
           *str++=ch;
           ch=getchar();
     }
     *str=0;
     return true;
}
    char forei[13];
int main()
{
    int i=1;
    while(myget(&english[i][0]))
    {
         myget(&foreign[i][0]);
         setHash(i);
         ++i;
    }
    while(myget(forei))
    {
         int h=myHash(forei);
         if(h==0)
           printf("eh\n");
         else
           printf("%s\n",english[h]);
    }
    return 0;
}

第四种解法 trie tree

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int index[1000100][26];
int length=0;
int value[1000100];
char english[100020][12];
inline bool myget(char *str)
{
     char ch=getchar();
     if(ch==' '||ch=='\n'||ch==EOF)
       return false;
     while(ch!=' '&&ch!='\n')
     {
           *str++=ch;
           ch=getchar();
     }
     *str=0;
     return true;
}

int main()
{
    int i=1;
    char foreign[12];
    while(myget(&english[i][0]))
    {
         myget(&foreign[0]);
         
         int j=0,start=0;
         while(foreign[j]!=0)
         {
               int next=foreign[j]-'a';
               if(index[start][next]==0)
                  index[start][next]=++length;
               start=index[start][next];
               ++j;
         }
         value[start]=i;
         ++i;
    }

    char forei[12];
    while(myget(forei))
    {
         int j=0,start=0;
         while(forei[j]!=0)
         {
               int next=forei[j]-'a';
               start=index[start][next];
               ++j;
         }
         
         start=value[start];        
         if(start==0)
           printf("eh\n");
         else
           printf("%s\n",english[start]);
    }
    return 0;
}