[字符串hash]poj 1200：Crazy Search

大致题意：
    给出两个数n,nc，并给出一个由nc种字符组成的字符串。求这个字符串中长度为n的子串有多少种。

 

大致思路：
    裸哈希之，将长度为n的子串看作 n位的 nc进制数，将问题转化为共有多少种数字。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int hash[30];
bool loc[20000000];
char str[1000000];
int main(){
    int n,m,cnt,sum,len,ans,i,j;
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(loc,0,sizeof(loc));
        memset(hash,0,sizeof(hash));
        scanf("%s",str);
        len=strlen(str);
        cnt=1;
        ans=0;
        for(i=0;i+n<=len;i++){
            sum=0;
            for(j=i;j<i+n;j++){
                if(!hash[str[j]-'a']){
                    hash[str[j]-'a']=cnt++;
                }
                sum*=m;
                sum+=hash[str[j]-'a'];
            }
            if(!loc[sum]){
                loc[sum]=1;
                ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}