POJ 1200 Crazy Search(字符串简单的hash)

#include <stdio.h>
#include <iostream>
using namespace std;

const int MAX = 16000005;
const int NUM = 260;


bool ha[MAX];//存储hash映射
char str[MAX];//存储元字符串
int num[NUM];//存储映射的数字

int main (void)
{

    int n,nc,sum,count=0,ans=0;

    memset(num,0,sizeof(num));
    memset(str,'\0',sizeof(str));
    memset(ha,false,sizeof(ha));

    scanf("%d%d",&n,&nc);
    scanf("%s",str);
    //将每一个字母映射到一个数字上，nc进制的数字
    for (int i = 0; str[i] != '\0'; i++)
    {
        if(num[str[i]]==0)
            num[str[i]]=++count;
        if(count == nc)break;
    }
    //将每个字串计算一个结果数字，然后判断其hash 是否已经映射过次数字
    //如果没映射过则ans加1这样就能找到有多少不重复的字串了。
    int len = strlen(str);
    for(int i = 0; i <= len-n; i++)
    {
        sum = 0;
        for (int j = 0; j < n; j++)
            sum = sum*nc+num[str[i+j]];
        if(!ha[sum])
        {
            ha[sum]=true;
            ++ans;
        }
    }
    printf("%d\n",ans);
    return 0;
}