poj2503Babelfish
Babelfish
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 40985Accepted: 17467
Description
You have just moved from Waterloo to a big city. The people here speak an incomprehensible dialect of a foreign language. Fortunately, you have a dictionary to help you understand them.
Input
Input consists of up to 100,000 dictionary entries, followed by a blank line, followed by a message of up to 100,000 words. Each dictionary entry is a line containing an English word, followed by a space and a foreign language word. No foreign word appears more than once in the dictionary. The message is a quence of words in the foreign language, one word on each line. Each word in the input is a quence of at most 10 lowerca letters.
Output
Output is the message translated to English, one word per line. Foreign words not in the dictionary should be translated as "eh".
Sample Input
dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay
atcay
ittenkay
oopslay
Sample Output
cat
eh
loops
Hint
Huge input and output,scanf and printf are recommended.
题意是
输⼊⼀个字典，字典格式为“英语à外语”的⼀⼀映射关系
然后输⼊若⼲个外语单词，输出他们的英语翻译单词，如果字典中不存在这个单词，则输出“eh”
输⼊输出都是你如果多输出⼀个回车就会结束的
这题竟然归为了hash所以我⽤的是hash的⽅法，其实就⽤简单的map函数就可以直接⽤了，map好像是1900MS左右，hash我⽤的是⼤约在1600MS左右
代码如下
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <vector>
练肺活量最有效方法#define MAX 14997
#define MAX 14997
using namespace std;
struct node
{
char ch[102];
char ch1[102];
};
vector<node>v[15000];
int hash ( char str1[] )
{
int i;
int len = strlen(str1);
int pos = 0;
for ( i = 0; i < len; i++ )
花市灯如昼{
pos = pos+(int)str1[i]*(1+ i);
}
return pos%MAX;
}
int find ( char ch[], char ch1[] )
{
if ( strcmp ( ch, ch1) == 0 )
{
return 1;
}
return 0;
12月3日是什么星座
}
int main()
{
char str[102], str1[102];
char a[200];
int i;
while ( gets(a) &&a[0]!='\0' )
{
/*Separating element 分离元素*/
sscanf ( a,"%s %s", str, str1) ;
int pos = hash ( str1 );
/
*Storage of data 储存数据*/
node temp;
strcpy( temp.ch, str );
strcpy( temp.ch1, str1 );
v[pos].push_back(temp);
}
while ( gets(a) &&a[0]!='\0' )
{
int pos = hash ( a );
int ok = 1;
for ( i = 0;i < v[pos].size(); i++ )
{
/*Fine the same elements 查找相同元素*/ if ( find( v[pos][i].ch1, a ) )
{
printf ("%s\n", v[pos][i].ch );
ok = 0;
break;
}
}
if ( ok == 1 )
{
printf("eh\n");
}
}
}
⽤字典树更省时
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef struct DicTrie
{
struct DicTrie *next[26];
char word[11];
int isWord;
}*Trie;
void inrtWord( Trie node, char *stc, char *str ) {
int id, i;
while ( *str )
{
id = *str-'a';
龙的象征意义if ( node->next[id] == NULL )
{
node->next[id] = new DicTrie;
node->next[id]->isWord = 0;
for ( i = 0;i < 26; i++ )
{
node->next[id]->next[i] = NULL;
}
}
node = node->next[id];
str++;
}
node->isWord = 1;
strcpy( node->word, stc );
}
char* SearchWord(Trie node,char* st)
{
int id;
while(*st)
{
id=*st-'a';
if(node->next[id]==NULL)
{
return "eh";
}
node=node->next[id];
st++;
}
if(node->isWord)
{
return node->word;
}
el
{
return "eh";
}
}
}
int main()
{
int i;
char stc[11], str[11], st[25];王小波小说
Trie node;
node = new DicTrie;
node->isWord = 0;
for ( i = 0;i < 26; i++ )
血糖高能吃
{
node->next[i] = NULL;
}
while ( gets(st) && st[0] != 0)
{
sscanf ( st,"%s %s", stc, str) ;
inrtWord(node, stc, str);
}
while ( ~scanf ( "%s", st ) )
{
2018年生肖char *sum = SearchWord(node, st); printf ( "%s\n" ,sum );
}
离休和退休的区别}
代码菜鸟，如有错误，请多包涵
