//把求sum部分的循环弄掉了，只要减去开头的加上末尾的就可以减少很多次乘法了

#include<iostream>
using namespace std;
bool hash[16000000]={0};
char text[1000000];
int c[128];
int main(){
	int n,nc,i,j=0,length,ans=1,sum=0,tp=1;
	scanf("%d%d%s",&n,&nc,text);
	length=strlen(text);
	for(i=0;text[i];i++){
		if(!c[text[i]]) c[text[i]]=++j;
		if(j==nc) break;
	}
	for(i=0;i<n;i++){//预处理一个sum
		sum=sum*nc+c[text[i]]-1;
		tp*=nc;
	}
	tp/=nc; hash[sum]=1;
	for(i=1;i<=length-n;i++){
		sum=(sum-(c[text[i-1]]-1)*tp)*nc+c[text[i+n-1]]-1; //用这个公式替换原来的循环
		if(!hash[sum]){
			hash[sum]=1;
			ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

• Re:你的哈希函数不错啊，借鉴了一下~ 帮你稍微改了下，效率稍稍有所提高 (25) HH_YT 2012-03-16 18:05:11