#include<iostream>
#include<string>
using namespace std;
typedef struct
{
	int next[26];
	bool stay;
	string f;
	void init()
	{
		memset(next,0,sizeof(next));
		stay=false;
	}
}trie;
trie t[500000];
int num;	
string f_str;//空格之后的,输入外文查询
char str[22];
char e[100000][11],f[100000][11];
void insert(char *s,string f)//s 外文 f 对应的英文
{
	int index=0;
	int len=strlen(s);
	for(int i=0;i<len;i++)
	{
		if(t[index].next[s[i]-'a']==0)
		{
			t[++num].init();
			t[index].next[s[i]-'a']=num;
			index=num;
		}
		else
		{
			index=t[index].next[s[i]-'a'];
		}
	} 
	
	t[index].stay=true;	
	t[index].f=f;//存储相应英文
//	cout<<t[index].f;
}
void find(string s)
{ 
	int index=0;
	int len=s.length();
	for(int i=0;i<len;i++)
	{
		if(t[index].next[s[i]-'a']!=0)
		{
			index=t[index].next[s[i]-'a'];
		}
		else 
			break;
	}
	if(t[index].stay==true)//有这个词
		cout<<t[index].f<<endl;
	else
		cout<<"eh"<<endl;
}
int main()
{
	int i=0;
	num=0;
	t[0].init();
	while(gets(str))
	{
		if(str[0]=='\0')
			break;
		sscanf(str,"%s %s",&e[i],&f[i]);
		insert(f[i],e[i]);//等下插入e[i]
		i++;
	}
	while(cin>>f_str)
	{
		find(f_str);
	}
	return 1;
}
/*
dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay
*/

• Re:内存超了,写了一个晚上的trie....求大牛帮忙优化~T T (37) blackRats 2013-08-01 01:48:34