本文主要是介绍POJ2503_Babelfish（字典树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Babelfish
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
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 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 is the message translated to English, one word per line. Foreign words not in the dictionary should be translated as "eh".
示例输入
dog ogday cat atcay pig igpay froot ootfray loops oopslayatcay ittenkay oopslay
示例输出
cat eh loops
解题报告
问题一开始出现在怎么输入，和结束输出上面，想了N久，想想如果一行两字串分开输入要用scanf（），可判断输入结束是当一行的字符串第一个为“\0”，这样就有问题了。。。
用gets（）的话，倒是可以结束输入，不过gets（）会整行储存的。。。
还没有计算时间复杂度，直接字符串比较。。。
结果超时了。。。
想想有什么办法做这题的，还省时间，哈希之类的查找应该可以，不过哈希函数不好写，然后就用上字典树，建字典树把那个字符串的下标也传进去，查找到的返回下标位置。。。
然后就MLE了，想想自己定义好多数组，删了好多还是MLE。。。
然后再把字符串的大小从1000改成30，就A了。。。
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
char ch[30];
char str[100000][30];
struct node
{int v;node *next[26];
};
node *newnode()
{node *p=new node;//动态分配//node *p=&T[t++];//静态分配p->v=0;for(int i=0; i<26; i++)p->next[i]=NULL;return p;
}
void insertnode(node *root,char *str,int n)//插入
{node *p=root;int l=strlen(str);for(int i=0; i<l; i++){int t=str[i]-'a';if(p->next[t]==NULL)p->next[t]=newnode();p=p->next[t];}p->v=n;
}
int find(node *root,char *str)//查找
{node *p=root;int l=strlen(str);for(int i=0; i<l; i++){int t=str[i]-'a';if(p->next[t]==NULL)return 0;p=p->next[t];}return p->v;
}
void freenode(node *root)
{node *p=root;for(int i=0;i<26;i++)if(p->next[i]!=NULL)freenode(p->next[i]);delete p;
}
int main()
{int i=0;node *root=newnode();while(gets(str[++i])!=NULL){if(str[i][0]=='\0')break;int k;for(k=0;str[i][k]!='\0';k++)if(str[i][k]==' ')break;insertnode(root,str[i]+k+1,i);}while(scanf("%s",ch)!=EOF){int r=find(root,ch);if(r){for(int e=0;str[r][e]!=' ';e++)printf("%c",str[r][e]);printf("\n");}else printf("eh\n");}freenode(root);}/**************************************Problem id : SDUT OJ 2693 User name : acm2013叶思俊 Result : Accepted Take Memory : 29264K Take Time : 90MS Submit Time : 2014-02-19 00:39:24
**************************************/
这篇关于POJ2503_Babelfish（字典树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
