poj 2503 哈希 Map 字典树

Description

Input

Output

Sample Input

dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay

Sample Output

cat
eh
loops

Hint

Source

//16096K 2625MS
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>

using namespace std;

int main()
{
	char s[100],s1[11];
	string ss;
	char c;
	map<string,string>Q;
	int num;
	while(gets(s)&&s[0]!='\0')  //读串比读多个字符快
	{
		int len=strlen(s);
		int i;
		for( i=0;i<len;i++)
		{
			if(s[i]==' ')
			{s[i]='\0';
			 break;
			}
		}
		ss=s+i+1;
		Q[ss]=s;
	}
	while(~scanf("%s",s1))
	{
		if(Q[s1].size())
			cout<<Q[s1]<<endl;
		else
			printf("eh\n");
	}
}
//	while(~scanf("%c",&c))  // 超时
//	{
//		if(c=='\n')
//			break;
//		num=0;
//		while(c!=' ')
//		{
//			s[num++]=c;
//			scanf("%c",&c);
//		}
//		s[num]='\0';   //够成字符串
//		num=0;
//		scanf("%c",&c);  //防止上一个空格被读入
//
//		while(c!='\n')
//		{
//			ss[num++]=c;
//			scanf("%c",&c);
//		}
//		ss[num]='\0';
//		Q[ss]=s;
//	}

//字典树 26240K    <span id="transmark"></span>735MS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>

using namespace std;

char ss[100],s[100],c[100010][100];
int num=0;
struct node
{
	int flag;
	node *next[26];
}*head;
node * Creat()
{
	node *p;
	p=new node;
	p->flag=0;
	for(int i=0;i<26;i++)
		p->next[i]=NULL;
	return p;
}
int Build_Tree()
{
	node *p=head;
    int len=strlen(s);
    for(int i=0;i<len;i++)
	{
		int a=s[i]-'a';
		if(!p->next[a])
		{
			p->next[a]=Creat();
			//p->next[a]->flag=num;
		}
		p=p->next[a];
	}
	p->flag=num;
}
int Find(char s1[])
{
	int len=strlen(s1);
	node *p=head;
	for(int i=0;i<len;i++)
	{
		int a=s1[i]-'a';
		if(!p->next[a])
		{
			return 0;
		}
		p=p->next[a];
	}
	return p->flag;
}
int main()
{
	num=1;
	head=Creat();
	while(gets(ss)&&ss[0]!='\0')
	{
		sscanf(ss,"%s %s",c[num],s);
		Build_Tree();
		num++;
	}
	char s1[100];
	while(~scanf("%s",s1))
	{
		int flag=Find(s1);
      //cout<<flag;
		if(flag)
			printf("%s\n",c[flag]);
		else
			printf("eh\n");
	}
}