Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
复习一下字符串哈希函数.#include<iostream> #include<string> #include<cstdio> using namespace std; struct Fish { string English; string Foreign; bool full; }x[150000]; //题目明明说最多十万条对不对?我写十万Runtime error了三次!改成十五万立马AC。唉~ int BKDRhash(string s) { int seed=131; unsigned int hash=0; string::iterator i=s.begin(); while(i!=s.end()) { hash=hash*seed+*i; ++i; } return hash%150000; } int main() { int index; string e,f; char ch='\n'; for(int i=0;i<100000;++i) { x[i].full=false; x[i].English="#"; x[i].Foreign="#"; } while(cin>>e>>f) { getchar(); if(ch!='\n') e.insert(e.begin(),ch); index=BKDRhash(f); if(!x[index].full) { x[index].English=e; x[index].Foreign=f; x[index].full=true; } else { while(x[index].full) index++; x[index].English=e; x[index].Foreign=f; x[index].full=true; } ch=getchar(); if(ch=='\n') break; } while(cin>>f) { index=BKDRhash(f); while(x[index].full&&x[index].Foreign!=f) index++; if(x[index].Foreign==f) cout<<x[index].English<<endl; else cout<<"eh"<<endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator