#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Trie
{
int id;
Trie* next[26];
} a[200005];
Trie root;
int id, locate;
void initial()
{
root.id= 0;
memset( root.next, 0, sizeof(root.next) );
id= 0;
locate= 0;
}
void insert( char* s )
{
Trie* r= &root;
while( *s )
{
int t= *s- 'a';
if( r->next[t]== NULL )
{
r->next[t]= a+ locate;
a[locate].id= -1;
memset( a[locate].next, 0, sizeof( a[locate].next ) );
locate++;
}
r= r->next[t];
s++;
}
if( r->id== -1 ) r->id= id++;
}
int search( char* s )
{
Trie* r= &root;
while( *s )
{
int t= *s- 'a';
if( r->next[t] ) r= r->next[t];
else return -1;
s++;
}
return r->id;
}
char str[100010][11];
int len= 0;
int main()
{
char s[50],s1[15];
initial();
while( gets(s), strlen(s)!= 0 )
{
sscanf(s,"%s %s",str[len++],s1);
insert( s1 );
}
while( gets(s)!= NULL )
{
int t= search(s);
if( t== -1 ) puts("eh");
else puts( str[t] );
}
return 0;
}
posted on 2008-11-25 10:54
Darren 閱讀(200)
評論(0) 編輯 收藏 引用