#include<stdio.h>
#include<string.h> 
/*
 * Macro 
 */
#define MAX_WORD_NUM 100000
#define MAX_WORD_LENGTH 10+1
#define PRIME_NUM 13

/*
 * declaration of structure
 */
typedef struct HashTable_struct{
	char value[MAX_WORD_LENGTH];
	char key[MAX_WORD_LENGTH];
}HashTable;
 
/*
 * declaration of functions
 */
 
int evalKey(char *p);
void insertTable(char *key,char* value);
int sfindValue(char *key);
/*
 * global variables
 */
HashTable hashTable[MAX_WORD_NUM];

/*
 * program entry
 */
int main()
{ 
	char english[MAX_WORD_LENGTH],dialect[MAX_WORD_LENGTH],line[MAX_WORD_LENGTH*2+1];
	int index;
	while(1){

		english[0]=(char)getchar();
		if(english[0]=='\n')break;
		scanf("%s %s",english+1,dialect);
		getchar();/* eat the ending '\n'*/

	/*insert this key-value pair into the hash table*/
		insertTable(dialect,english);
	}
	while(scanf("%s",dialect)!=EOF){
		index=findValue(dialect);
		if(index>=0)
			printf("%s\n",hashTable[index].value);
		else
			printf("eh\n");
	}
}


/*
 *  definition of functions
 */
 /*hash the string*/
int evalKey(char *p){
	int key=0; 
	while(*p){
		key+=(*p++)*PRIME_NUM;
		key=key%MAX_WORD_NUM;
	}
			
	return key; 
}

/*insert the key-value pair into the hash table*/
void insertTable(char *key,char *value){
	int keyNum=evalKey(key);
	while(hashTable[keyNum].key[0]!='\0'){
		keyNum++;
		keyNum=keyNum%MAX_WORD_NUM;
	}
		
	strcpy(hashTable[keyNum].key,key);
	strcpy(hashTable[keyNum].value,value);
	
}

/*given a key, find the position of this key , return -1 if not found*/
int findValue(char *key){
	int keyNum=evalKey(key);
	
	while(hashTable[keyNum].key[0]!='\0'){
		if(strcmp(hashTable[keyNum].key,key)==0)
			return keyNum;
		
		keyNum++;
		keyNum=keyNum%MAX_WORD_NUM;
	}
	
	return -1;

• Re:TLE 哪位好心人帮忙看一下瓶颈在那里，该怎么改进？ (52) xemo 2005-08-31 08:24:33
  • Re:TLE 哪位好心人帮忙看一下瓶颈在那里，该怎么改进？ (167) ykt 2005-08-31 10:19:25
• 把你的 输入改了一下，是wa~..偶用trie做的~ (230) tend 2005-08-31 15:30:11
  • 手头没有VC，我用这个马甲边改边交的...不保证改的没错误 (254) tend 2005-08-31 15:30:56
    • Re:手头没有VC，我用这个马甲边改边交的...不保证改的没错误 (335) ykt 2005-08-31 16:17:35
      • Re:....哦哦哦，说错了....最后我用的cin...gets()的我是在中间去空格的~不好意思~ (347) mixter 2005-08-31 16:42:09
        • 见内，偶把偶2次的输入搞混了...注释掉的是用gets的...汗 (547) mixter 2005-08-31 16:53:10
      • 哦~还是TLE (1696) tend 2005-08-31 16:50:54
• Re:TLE 哪位好心人帮忙看一下瓶颈在那里，该怎么改进？ (161) ykt 2005-08-31 16:38:35
  • 汗~ 。。。。呵呵 (187) tend 2005-08-31 16:51:25