首页 > 代码库 > poj 2503:Babelfish(字典树,经典题,字典翻译)
poj 2503:Babelfish(字典树,经典题,字典翻译)
Babelfish
Time Limit: 3000MS | Memory Limit: 65536K | |
Total Submissions: 30816 | Accepted: 13283 |
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 sequence of words in the foreign language, one word on each line. Each word in the input is a sequence of at most 10 lowercase 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 ogdaycat atcaypig igpayfroot ootfrayloops oopslayatcayittenkayoopslay
Sample Output
catehloops
Hint
Huge input and output,scanf and printf are recommended.
Source
Waterloo local 2001.09.22
字典树,经典题,字典翻译。
这道题和 hdu 1075:What Are You Talking About 很像,只不过那道题是翻译句子,这道题是翻译单词。之前做过类似的题做这道题的时候就比较轻松了。
题意:给你若干个单词以及其对应的翻译作为字典,然后再给你若干单词,根据之前的字典求他们的翻译,若没有,则输出eh。
思路:将字典中的单词插入到字典树中,在最后一个节点上加上其翻译单词。查找的时候只要找到了这个单词最后这个节点,且这个节点上的存储翻译单词的域不为空说明存在翻译,输出其翻译,如果域为空,则输出“eh”。
代码:
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 5 using namespace std; 6 struct Tire{ 7 Tire *next[26]; 8 char *trans; 9 Tire()10 {11 int i;12 for(i=0;i<26;i++)13 next[i] = NULL;14 trans = NULL;15 }16 } root;17 18 void Insert(char word[],char trans[])19 {20 Tire *p = &root;21 int i;22 for(i=0;word[i];i++){23 int t = word[i] - ‘a‘;24 if(p->next[t]==NULL)25 p->next[t] = new Tire;26 p = p->next[t];27 }28 p->trans = new char[11];29 strcpy(p->trans,trans);30 }31 32 void Find(char word[]) //查找该单词的翻译并输出,如果没有则输出eh33 {34 Tire *p = &root;35 int i;36 for(i=0;word[i];i++){37 int t = word[i] - ‘a‘;38 if(p->next[t]==NULL){39 printf("eh\n");40 return ;41 }42 p = p->next[t];43 }44 if(p->trans!=NULL)45 printf("%s\n",p->trans);46 else //没找到47 printf("eh");48 }49 50 int main()51 {52 char str[11];53 while(gets(str)){54 if(str[0]==‘\0‘) //检测到空行55 break;56 char trans[11],word[11];57 sscanf(str,"%s%s",trans,word);58 Insert(word,trans);59 }60 while(scanf("%s",str)!=EOF) //读取要翻译的单词61 Find(str);62 return 0;63 }
Freecode : www.cnblogs.com/yym2013
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。