#include<stdio.h>
#include<string.h>

#define size 160

char* hash[size+1];
char s[size+10];
int N,NC;

bool hashfind(int k)
{
	int t=1,index = ((s[k]+19)*(s[k]+131)*((s[k+N-1]+3331)>>1)*31)%size;
	if(index<0) index = (index+214748367)%size;
	while(hash[index] && (t=strncmp(hash[index],s+k,N))!=0) index++;
	if(t) { hash[index] = s+k; return true; }
	return false;
}

int solve()
{
	int i,res=0;
	int len = strlen(s);
	len = len-N+1;
	for(i=0;i<len;i++)
		if(hashfind(i)) res++;
	return res;
}

int main()
{
	if(!freopen("1200.in","r",stdin)) return 1; 
	scanf("%d%d",&N,&NC);
	scanf("%s",s);
	printf("%d\n",solve());
	return 1;
}

• 怎么做HASH啊，各位大大。。。。 (0) 003 2005-09-19 21:15:39