poj1200 题意:求一个字符串中,长度为n的字串的种类
标准哈希【捂脸】..我的哈希…感觉…有待改进【捂脸】
#include <cstdio>
#include <cstring>
#define N 17000000
char s[N];
int ans=
0,n,m,len,num=
0,hash[N],flag[N];
unsigned
long long sum=
0,k=
1;
int main(){
scanf(
"%d%d%s",&n,&m,s+
1);len=strlen(s+
1);
for(
int i=
1;i<=len;i++)
if(!flag[s[i]]) flag[s[i]]=++num;
for(
int i=
1;i<=n;i++)
sum=
sum*m+flag[s[i]]-
1,k*=m;
k/=m;hash[
sum]=
1;ans++;
for(
int i=n+
1;i<=len;i++){
sum=(
sum-(flag[s[i-n]]-
1)*k)*m+flag[s[i]]-
1;
if(!hash[
sum]) hash[
sum]=
1,ans++;
}printf(
"%d\n",ans);
return 0;
}