| ||||||||||
| 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