#include <stdio.h>
#include <string.h>
//#include <windows.h>

#define MAXN 100000
#define Prime 3999971

typedef struct _dir{
	char F[11];
	char E[11];
}DIR;

unsigned char hash[Prime];
DIR dir[MAXN+2];

int hashcode(char *str) // 0.35
{
	int hash=0,x = 0,i;
	int n = strlen(str);
	
	for (i = 0; i <n; i++) {
		hash = (hash <<4) + str[i];
		if ((x = hash & 0xf0000000) != 0) {
			hash ^= (x>> 24);
			hash &= ~x;
		}
	}
	hash %= Prime;
	if(hash<0)hash += Prime;
	return hash;
}


// int hashcode(char *str)
// {
// 	int n = strlen(str);
// 	int hash = n;
// 	int i;
// 	for(i=0;i<n;i++)
// 	{
// 		hash *= (str[i]-'a'+1);
// 	}
// 	hash %= Prime;
// 	if(hash<0)hash+=Prime;
// 	return hash;
// }

int main()
{
	int i=1;
	int p;
	char str[30];
//	long start = GetTickCount();
	freopen("in.txt","r",stdin);

	while (1)
	{
		gets(str);
		if(!strlen(str))break;
		sscanf(str,"%s%s",dir[i].E,dir[i].F);
		p = hashcode(dir[i].F);
		while (hash[p]!=0)
		{
			p++;
			p %= Prime;
		}
		hash[p] = i++;
	}
	//scanf("%*c");
	while(scanf("%s",str)!=EOF)
	{
		p = hashcode(str);
		while (hash[p]!=0)
		{
			if (!strcmp(str,dir[hash[p]].F))
			{
				printf("%s\n",dir[hash[p]].E);
				break;
			}
			p++;
			p%=Prime;
		}
		if (hash[p]==0)printf("eh\n");
	}
//	printf("%d ms\n",GetTickCount()-start);
	return 0;
}

• Re:也很郁闷。也是标准hash。。一直TLE (266) yayu_myself 2011-01-25 01:06:39
  • Re:也很郁闷。也是标准hash。。一直TLE (13) PrinceFrost 2012-09-10 09:58:19