PKU 3193 Cow Phrasebook
http://poj.org/problem?id=3193
m個の文字列が与えられる。
その後に、n個の文字列が与えられる。
このn個の文字列のうち、最初に与えられたm個のprefixになっているものは何個あるかを数えろというような問題。
ハッシュつかいました。
高速な入力をつかいました。
実行時間がかなり早くてうれしくなりました。
typedef struct _node{ char *key; int len; _node*next; }node; const int hashMod=300000; node* hash[hashMod]; node ent[100000]; int sz; void insert(char *str){ int ha=0; int len=0; while(str[len]){ ha=(ha*67+str[len])%hashMod; ++len; bool ok=false; for(node*p=hash[ha];p;p=p->next){ if(p->len==len && strncmp(p->key,str,len)==0){ ok=true; break; } } if(ok)continue; node*p=hash[ha]; hash[ha]=ent+sz++; hash[ha]->key=str; hash[ha]->len=len; hash[ha]->next=p; } } int app(char *str){ int ha=0; int len=0; for(;str[len];++len)ha=(ha*67+str[len])%hashMod; for(node*p=hash[ha];p;p=p->next) if(p->len==len && strncmp(p->key,str,len)==0)return 1; return 0; } char input[1000000]; char*pos; char*getstr(){ while(*pos=='\n' || *pos=='\r' || *pos==0)++pos; char*ret=pos; while(*pos!='\n' && *pos!='\r')++pos; *pos=0; return ret; } int getnum(){ int ret=0; while(!isdigit(*pos))++pos; ret=*pos++&15; while(isdigit(*pos))ret=(ret<<3)+(ret<<1)+(*pos++&15); return ret; } main(){ fread(input,sizeof(input),1,stdin); pos=input; int m=getnum(); int n=getnum(); rep(i,m)insert(getstr()); int ans=0; rep(i,n)ans+=app(getstr()); printf("%d\n",ans); }