考前复习——字符串哈希与哈希表

#include<bits/stdc++.h>
using namespace std;

#define N 1005
#define ULL unsigned long long
#define Base 13331

int n;
ULL h[N][N],q[N];
char ch[N][N];

inline int read()
{
	int x=0;
	bool f=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar())
		if(ch=='-')
			f=0;
	for(;isdigit(ch);ch=getchar())
		x=(x<<1)+(x<<3)+ch-'0';
	return f?x:(~(x-1));
}

void Hash(int k)
{
	//计算第k个字符串的哈希值 
	ULL len=strlen(ch[k]+1);
	for(ULL i=1;i<=len;i++)
	{
		h[k][i]=h[k][i-1]*Base+(ch[k][i]-'A');
	}
	return ;
}

ULL ck(ULL h[],int l,int r)
{
	//获取该字符串[l,r]区间的哈希值 
	return h[r]-h[l-1]*q[r-l+1];
}

int main()
{
	cin>>n;//几个字符串
	q[0]=1;
	for(int i=1;i<N;i++)q[i]=q[i-1]*Base;
	for(int i=1;i<=n;i++)
	{
		scanf("%s",ch[i]+1);
		Hash(i);
	}
//	cout<<ck(h[1],1,3)<<" "<<ck(h[2],4,6);
	return 0;
}