PKU 2872 Spelling Be
http://poj.org/problem?id=2872
辞書とメールの内容が渡される。メールに辞書にない単語があればそれを検出しろというような問題。
やるだけだといいなと思いながらサブミットするとTLEになったので、ハッシュゲーへと変わりました。
入力形式を勘違いして何回かWAりました。
typedef struct _node{ char key[200]; _node*next; }node; node ent[100000]; int sz; const int MOD=100007; node*hash[MOD]; bool find(char in[]){ int ha=0; for(char*p=in;*p;++p)ha=(ha*37+*p)%MOD; for(node*p=hash[ha];p;p=p->next) if(strcmp(p->key,in)==0)return true; return false; } bool insert(char in[]){ int ha=0; for(char*p=in;*p;++p)ha=(ha*37+*p)%MOD; for(node*p=hash[ha];p;p=p->next) if(strcmp(p->key,in)==0)return true; node*p=hash[ha]; hash[ha]=ent+sz++; strcpy(hash[ha]->key,in); hash[ha]->next=p; return false; } char st[200]; main(){ int t; scanf("%d",&t); rep(i,t){ scanf(" %s ",st); insert(st); } scanf("%d",&t); int ca=0; while(t--){ ++ca; vector<string>ans; while(cin>>st){ if(strcmp(st,"-1")==0)break; if(!find(st))ans.pb(st); } if(ans.empty())cout<<"Email "<<ca<<" is spelled correctly."<<endl; else{ cout<<"Email "<<ca<<" is not spelled correctly."<<endl; FOR(iter,ans)cout<<*iter<<endl; } } cout<<"End of Output"<<endl; }