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
yessirloops
Hint
Huge input and output,scanf and printf are recommended.
题意是
输⼊⼀个字典，字典格式为“英语à外语”的⼀⼀映射关系
然后输⼊若⼲个外语单词，输出他们的英语翻译单词，如果字典中不存在这个单词，则输出“eh”
输⼊输出都是你如果多输出⼀个回车就会结束的
这题竟然归为了hash所以我⽤的是hash的⽅法，其实就⽤简单的map函数就可以直接⽤了，map好像是1900MS左右，hash我⽤的是⼤约在1600MS左右
代码如下
#include <stdio.h>
the namir#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;
吸血鬼日记第八季结局
}
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";
}
}
}
英语flash
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 ) )
{
char *sum = SearchWord(node, st); printf ( "%s\n" ,sum );
深圳翻译公司
}
}
代码菜鸟，如有错误，请多包涵
