学步园

题目链接：   http://poj.org/problem?id=1200

题目大意：  给出两个数字N和NC，一行字符串

                    这行字符串最多出现NC个字符

                    寻找长度为N的不同子串个数

解题思路：   字符串的长度最长为1600万，用strcmp()函数判断次数太多，肯定会TLE

                    开始用了BKDRHask，和ELFHask都WA，说明有些字串的hash值相等

                    为了避免这种情况我用链表来处理冲突，但是爆内存了，原因是数组太大！

                    最后把问题转化成NC进制，AC了

                    这道题可以用一个很巧妙的方法，将数值降到最小：

           如：

                    3 3

                    abcabc

                    abc：1x3^2+2x3^1+3x3^0=18

                    bca：2x3^2+3x3^1+1x3^0=28

                    cab：3x3^2+1x3^1+2x3^0=32

                    abc：1x3^2+2x3^1+3x3^0=18

                    3

代码：

//hash基础题, 转化为 nc进制
#include <stdio.h>
#include <string.h>
#define MAX 1600000
char ch[MAX];
int Hash[MAX*10]={0},a[256]={0};
int main()
{
    int i,j,h,t,n,nc,num;
    scanf("%d%d%s",&n,&nc,ch);
    memset(a,-1,sizeof(a));
    for(i=0;ch[i]!='\0';i++)
    {
        if(a[ch[i]]==-1)
        {
            a[ch[i]]=1;
        }
    }
    for(i=0,num=0;i<256;i++)
    {
        if(a[i]!=-1)
            a[i]=num++;     //***减少数的大小,防止数组不够大,从0开始！
    }
    for(i=0,t=0;ch[i+n-1]!='\0';i++)
    {
        h=0;
        for(j=i;j<i+n;j++)
        {
            h=h*nc+a[ch[j]];
        }
        if(!Hash[h])  //判断之前是否存在
        {
            Hash[h]=1;
            t++;    //新加入的标记
        }
    }
    printf("%d\n",t);
    return 0;
}

注：原创文章，转载请注明出处