Crazy Search （哈希算法）

Crazy Search

---

给定一个字符串，其中含有不同的字母数量为m，现在求这个字符串中有多少个长度为n且长的互不相同的字符子串
举个例子, n=3, m=4 ，字符串 “daababac”. 长度为3的不同的子串分别是: “daa”; “aab”; “aba”; “bab”; “bac”. 因此, 答案是5.

---

Input
第一行是两个整数n,m,，一个空格隔开。 接下来一行是我们要解决的字符串.（ 你可以认为字符串的长度不会超过一千六百万。）Orz我读错题了，并不是字符串长度不超过1600万，是合理hash之后的hash的值不超过1600万。Orz原谅我

---

Output
程序应该输出一个整数，对应于给定文本中所找到的大小为n的不同子字符串的数量。

---

输入数据
3 4
daababac

---

输出数据
5

---

提示
输入数据量庞大，推荐使用scanf

---

#include <cstdio>
#include<string>
#include<cstring> 
using namespace std;
//typedef unsigned long long ull;
//const ull mod=1e9+7;
bool Hash[16000001];
int w[500];
char s[16000001];
int main(){
    int n,nc,cnt,ans,i,j,l,sum;
    while(~scanf("%d%d",&n,&nc)){
        cnt=0;
        ans=0;
        memset(w,-1,sizeof(w));
        memset(Hash, false, sizeof(Hash));
        scanf("%s",s);
        l=strlen(s);
        for(i=0;i<l&&cnt<nc;i++)
            if(w[s[i]]==-1)
                 w[s[i]]=cnt++;
        for(i=0;i<l-n+1;i++){
            sum=0;
            for(j=i;j<i+n;j++)
                 sum=sum+sum*nc+w[s[j]];
//                sum=sum%mod+sum*nc+w[s[j]]%mod;   防止超时 
            if(!Hash[sum]){
                 ans++;
                 Hash[sum]=true;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}