poj-2503-Babelfish-字典樹

poj-2503-Babelfish-字典樹

//做了幾道trie得出了一條結論,,,當單詞的長度超過15時,,適合hash,,,不超過15時適合trie,,,,

//因為trie的常數主要乘在了單詞長度的循環上,,,,,而hash在這個循環的常數基本是1,,,但是hash此外需要處理沖突,,單詞越長,,發成沖突的可能性就越小,,解決沖突的時間就越短,,,,

//使用trie有一個隱患,,,,如果用動態內存容易超時,,,用靜態內存容易超內存
//http://blog.csdn.net/whyorwhnt/article/details/8723737
#include
#include
#include
#include
using namespace std;
struct node
{
	char word[15];  //存放翻譯後的英語 
	int next[30];
}tire[100005*15];

int e;

void  insert(char s[],char ch[])
{
	int t=0;
	
	for(int i=0;ch[i];i++)
	{
		if(tire[t].next[ch[i]-'a'] ==0 )
		{
			tire[t].next[ch[i]-'a']=++e;
		}
		t=tire[t].next[ch[i]-'a'];
	}
	strcpy(tire[t].word,s);
}

void output(char str[])
{
	int t=0;
	
	for(int i=0;str[i];i++)
	{
		if(tire[t].next[str[i]-'a'] ==0 )
		{
			printf(eh
);
			return; 
		}
		t=tire[t].next[str[i]-'a'];
	}
	printf(%s
,tire[t].word);
}

int main()
{
	char ch[30],str1[15],str2[15];
	
	e=1;
	//freopen(read.txt,r,stdin);
	//memset(next,0,sizeof(next));
	while(gets(ch))
	{
		if(ch[0]==0)
		  break;
		sscanf(ch,%s%s,str1,str2);
		insert(str1,str2); 
	}
	while(gets(ch))
	{
		output(ch);
	}
	return 0;
}