首页 > 代码库 > QuicksearchTries2503

QuicksearchTries2503

2024-07-26 01:25:00   214人阅读

输入一个字典，字典格式为“英语à外语”的一一映射关系

然后输入若干个外语单词，输出他们的 英语翻译单词，如果字典中不存在这个单词，则输出“eh”

 

poj2503题目意思很简单：就像查找一本字典，根据输入的条目和要查询的单词，给出查询结果（每个单词长度不超过10）。这题有很多实现方式，最容易想到的就是map，但这是acm训练且stl里面的map速度不够快，那就要另谋出路。

 

 

 

 

自己AC通过的#include<cstdio>#include<cstring>int num;char des[100001][11];class tirenode{public:	tirenode * next[26];	int id;	tirenode()	{		memset(next,0,sizeof(next));		id=0;	}}root;void insert(char ch1[],char ch2[]){	tirenode *p=&root;	int i=0;	while(ch2[i])	{		if(p->next[ch2[i]-‘a‘]==0)		{			p->next[ch2[i]-‘a‘]=new tirenode;		}		p=p->next[ch2[i]-‘a‘];		i++;	}	if(p->id==0)//如果还没存在这个单词	{		num++;		p->id=num;		strcpy(des[num],ch1);	}}int find(char ch3[]){	tirenode *p=&root;	int i=0;	while(ch3[i])	{		if(p->next[ch3[i]-‘a‘]==0)		{			printf("eh\n");			return 1;		}		p=p->next[ch3[i]-‘a‘];		i++;	}	if(p->id==0)		printf("eh\n");	else printf("%s\n",des[p->id]);	return 1;}int main(){	char chch[22],ch1[11],ch2[11];	int i,j;	num=0;	while(gets(chch) && chch[0])	{		for(i=0;chch[i]!=‘ ‘;i++)			ch1[i]=chch[i];		ch1[i]=0;		i++;		j=0;		for(;chch[i];i++)			ch2[j++]=chch[i];		ch2[j]=0;		insert(ch1,ch2);//		printf("%s\t%s",ch1,ch2);	}	while(gets(chch))	{		find(chch);	}	return 1;}

　　

QuicksearchTries2503


联系
我们