poj-2503-Babelfish-字典树

题目链接：http://poj.org/problem?id=2503

//做了几道trie得出了一条结论,,,当单词的长度超过15时,,适合hash,,,不超过15时适合trie,,,,

//因为trie的常数主要乘在了单词长度的循环上,,,,,而hash在这个循环的常数基本是1,,,但是hash此外需要处理冲突,,单词越长,,发成冲突的可能性就越小,,解决冲突的时间就越短,,,,

//使用trie有一个隐患,,,,如果用动态内存容易超时,,,用静态内存容易超内存
//http://blog.csdn.net/whyorwhnt/article/details/8723737
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
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\n");
			return; 
		}
		t=tire[t].next[str[i]-'a'];
	}
	printf("%s\n",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;
}

poj-2503-Babelfish-字典树

原文：http://blog.csdn.net/holyang_1013197377/article/details/45102227