POJ 2503 Babelfish 字典树经典题 三种方法 (map,排序+二分,字典树)

题意很简单：每给定两个单词，要找后一个单词相对应的单词，找不到则输出eh。

很容易联想到map，这里就当练习下map的使用。

参考博客：点击打开链接

#include<iostream> #include<algorithm> #include<queue> #include<vector> #include<string> #include<cstring> #include<cstdio> #include<map> const int maxn=100005; const int INF=0x3f3f3f3f; typedef long long LL; using namespace std; int main() { // freopen("E:\\ACM\\test.txt","r",stdin); map<string,string> m; string s; char str[100],s1[100],s2[100]; while(gets(str)) { if(strlen(str)==0) break; sscanf(str,"%s %s",s1,s2); //意思是将str通过空格分离为字符串s1和s2 m[s2]=s1; } while(cin>>s) { string c=m[s]; if(c.size()==0) puts("eh"); else cout<<c<<endl; } return 0; }

排序+二分

#include<iostream> #include<algorithm> #include<queue> #include<vector> #include<string> #include<cstring> #include<cstdio> const int maxn=100005; const int INF=0x3f3f3f3f; typedef long long LL; using namespace std; struct Node { char e[20],f[20]; }d[maxn]; int n; //单词总数 bool cmp(Node a,Node b) { return strcmp(a.f,b.f)<0; } int search(char *s) { int l=0,r=n-1; while(l<=r) { int m=(l+r)/2; if(strcmp(d[m].f,s)==0) return m; else if(strcmp(d[m].f,s)>0) r=m-1; else l=m+1; } return -1; } int main() { // freopen("E:\\ACM\\test.txt","r",stdin); char str[100]; n=0; while(gets(str)) { if(strlen(str)==0) break; sscanf(str,"%s %s",d[n].e,d[n].f); //意思是将str通过空格分离为字符串s1和s2 ++n; } sort(d,d+n,cmp); while(cin>>str) { int t=search(str); if(t==-1) puts("eh"); else cout<<d[t].e<<endl; } return 0; } 参考：点击打开链接

字典树，经典题，字典翻译。 这道题和 hdu 1075:What Are You Talking About 很像，只不过那道题是翻译句子，这道题是翻译单词。之前做过类似的题做这道题的时候就比较轻松了。

思路：将字典中的单词插入到字典树中，在最后一个节点上加上其翻译单词。查找的时候只要找到了这个单词最后这个节点，且这个节点上的存储翻译单词的域不为空说明存在翻译，输出其翻译，如果域为空，则输出“eh”。

#include<iostream> #include<string> #include<cstring> #include<cstdio> using namespace std; struct Tire { Tire *next[26]; char *trans; //存储翻译单词 Tire() { memset(next,0,sizeof(next)); trans=NULL; } }root; void insert(char *s,char *trans) { Tire *p=&root; for(int i=0;s[i];i++) { int index=s[i]-'a'; if(!p->next[index]) p->next[index]=new Tire; p=p->next[index]; } p->trans=new char[11]; ;//开辟一个存放字符数组(包括10个元素)的空间 strcpy(p->trans,trans); //在这个单词最后存储翻译单词 } void find(char *s) { Tire *p=&root; for(int i=0;s[i];i++) { int index=s[i]-'a'; if(!p->next[index]) //没找到 { puts("eh"); return ; } p=p->next[index]; } printf("%s\n",p->trans); //找到该单词，输出翻译单词 } int main() { // freopen("E:\\ACM\\test.txt","r",stdin); char s[11],s1[11],s2[11]; while(gets(s)) { if(strlen(s)==0) break; sscanf(s,"%s %s",s1,s2); insert(s2,s1); } //询问 while(scanf("%s",s)!=EOF) find(s); return 0; }

放张图，对比对比。

依次是字典树，排序+二分，和map。