POJ-1200 Crazy Search,人生第一道hash题！

                                                    Crazy Search

真是不容易啊，人生第一道hash题竟然是搜博客看题解来的。

题意：给你一个包含m种字符的字符串，求长度为n的不同子串有多少个。

将每个字串化为一个具体的数然后存入数组标记即可，如果重复出现肯定不用再加了。那么怎么化为一个数呢，这里用的方法是先将每个字符对应一个数，然后每个长度为n的子串就有了一个连续的数，将这个数段转化为m进制下的数即可，时间复杂度是O(len)。注意数据范围！

虽然和网上很多代码思路都是一样的，毕竟是自己理解的结晶，日后回过头回顾回顾也是很欣慰的！

const int N=1e7;

const double eps=1e-4;

const double PI=acos(-1.0);

char str[N];

int fuck[256];

bool v[N];

int main()

{

    int n,m;

    while(~scanf("%d%d%s",&n,&m,str))

    {

        int len=strlen(str);

        memset(fuck,0,sizeof(fuck));

        memset(v,false,sizeof(v));

        int x=0;

        for(int i=0;i<len;i++)

            if(!fuck[str[i]]) fuck[str[i]]=x++;

        int pow=1,sum=0;

        for(int i=1;i<n;i++) pow*=m;

        for(int i=0;i<n;i++)  sum=sum*m+fuck[str[i]];

        int res=0;

        if(!v[sum])

        {

            v[sum]=true;

            res++;

        }

        for(int i=n;i<len;i++)

        {

            sum-=fuck[str[i-n]]*pow;

            sum=sum*m+fuck[str[i]];

            if(!v[sum])

            {

                res++;

                v[sum]=true;

            }

        }

        printf("%d\n",res);

    }

    return 0;

}