UVA - 10282 Babelfish （字符串hash）

2019-11-06 08:05:23

字体：大中小

来源：转载

供稿：网友

字符串hash模板题字符串hash模板

int get_hash(char *s){ int seed=131;//可以用其他代替 int hash=0; for(int i=0;s[i]!='/0';i++) { hash=hash*seed+(s[i]-'a'); } return (hash & 0x7FFFFFFF)%mod; //mod取最大素数}

AC代码：

#include<stdio.h>#include<string.h>#include<vector>using namespace std;#define mod 100003char flag[100007][50];char aim[100007][50];int next1[100007];int first[100007];int get_hash(char *s){ int seed=131; int hash=0; for(int i=0;s[i]!='/0';i++) { hash=hash*seed+(s[i]-'a'); } return (hash & 0x7FFFFFFF)%mod;}void add_hash(int s){ int h=get_hash(aim[s]); next1[s]=first[h]; first[h]=s;}int main(){ char a[101]; int t=0; memset(next1,-1,sizeof(next1)); memset(first,-1,sizeof(first)); while(gets(a)&&a[0]!='/0') { int i; for(i=0;a[i]!=' ';i++) { flag[t][i]=a[i]; } flag[t][i]='/0'; int tt=0; i++; while(a[i]!='/0') { aim[t][tt++]=a[i++]; } aim[t][tt]='/0'; add_hash(t); t++; } char st[101]; while(gets(st)) { int h=get_hash(st); h=first[h]; int flog=0; while(h!=-1) { if(strcmp(aim[h],st)==0) { PRintf("%s/n",flag[h]); flog=1; break; } h=next1[h]; } if(!flog) printf("eh/n"); }}

上一篇：静态顺序表------C语言实现

下一篇：6访问权限控制