首页 > 代码库 > POJ2503 Babelfish map或者hash_map
POJ2503 Babelfish map或者hash_map
POJ2503 这是一道水题,用Map轻松AC。
不过,可以拿来测一下字符串散列, 毕竟,很多情况下map无法解决的映射问题需要用到字符串散列。
自己生成一个质数, 随便搞一下。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string.h> #include<cmath> #include<vector> #include<algorithm> using namespace std; const int maxn=1e+6; const int P=999983; unsigned int base[100]; int dic[maxn]; char eng[100010][11]; inline void init_hash(char* s,int h[]) { int l=strlen(s); h[0]=0; for(int i=1;i<=l;++i) { h[i]=(h[i-1]*26+s[i-1])%P; } base[0]=0; for(int i=1;i<=l;i++) base[i]=(base[i-1]*26)%P; } inline unsigned int string_hash(char* s,int h[], int l, int r)//[l,r)左闭右开 { init_hash(s,h); return (h[r]-h[l]*base[r-1])%P; } int ha[maxn]; int main() {freopen("t.txt","r",stdin); //ios::sync_with_stdio(false); memset(dic,0,sizeof(dic)); char lan[11]; int ditlen=1,tot=0; eng[0][0]=‘e‘; eng[0][1]=‘h‘; eng[0][3]=‘\0‘; while(true) { char t=getchar(); if(t==‘\n‘)break; int len=1; eng[ditlen][0]=t; while(true) { t=getchar(); if(t==‘ ‘){eng[ditlen][len++]=‘\0‘;ditlen++;break;} eng[ditlen][len++]=t; } int lent=0; while(true) { t=getchar(); if(t==‘\n‘){lan[lent++]=‘\0‘;break;} lan[lent++]=t; } int leng=strlen(lan); int has=string_hash(lan,ha,0,leng); while(has<0)has+=P; dic[has]=ditlen-1; } while(scanf("%s",lan)!=EOF) { int has=string_hash(lan,ha,0,strlen(lan)); while(has<0)has+=P; has=dic[has]; for(int i=0;;i++) { if(eng[has][i]==‘\0‘)break; printf("%c",eng[has][i]); } printf("\n"); } return 0; }
POJ2503 Babelfish map或者hash_map
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。