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);
}