首页 > 代码库 > POJ 2503 Babelfish
POJ 2503 Babelfish
字典树问题(map可水)
题意是:给你一本字典,叫你翻译一段话。
先把对应关系找到,然后输出就可以。字典树用于返回这是出现的第几个未知单词,然后对应。
可以用map水过去。
Trie:
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 #define LL long long using namespace std; struct Trie { int word[100001][26]; int sz,cot; int ex[1000001]; Trie() { sz=1; cot=1; memset(word,0,sizeof(word)); memset(ex,0,sizeof(ex)); } int insert(char *s) { int u=0,c,len=strlen(s); for(int i=0; i<len; i++) { c=s[i]-'a'; if(!word[u][c]) word[u][c]=sz++; u=word[u][c]; } if(ex[u]==0)ex[u]=cot++; return ex[u]; } int search(char *s) { int u=0,c,len=strlen(s); for(int i=0;i<len;i++) { c=s[i]-'a'; if(word[u][c]) u=word[u][c]; else return 0; } return ex[u]; } }wo; char str[100001][11]; int main() { char tmp[25]; char a[11],b[11]; while(gets(tmp),*tmp) { sscanf(tmp,"%s %s",a,b); int m=wo.insert(b); sscanf(a,"%s",str[m]); } while(scanf("%s",a)!=EOF) { int m=wo.search(a); if(m==0)puts("eh"); else puts(str[m]); } }
map:
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 #define LL long long using namespace std; map<string,string>word; int main() { string a; char str[51]; char sa[11],sb[11]; while(gets(str),*str) { sscanf(str,"%s %s",sa,sb); word[sb]=sa; } while(cin>>a) { if(word.find(a)==word.end()) puts("eh"); else cout<<word[a]<<endl; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。