Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

复习一下字符串哈希函数.

Posted by 139074241 at 2015-01-31 15:08:51 on Problem 2503
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator