poj 1200 Crazy Search字符串hash

 這個題是求一個字符串裡面出現了多少個長度為N的不同子串，同時給出了母串裡面不同字符
的個數NC。
   保存子串到set裡面直接暴力肯定超時了。這個題有個利用字符串hash的解法，雖然理論上有
bug，但是能過這個題。
   利用給出的NC，對長度為N的字符串，將其當作NC進制的數字，求出其值，對值進行hash，
求出不同的hash位置個數。
   這個算法其實類似於Karp-Rabin字符串匹配算法。不過，Karp-Rabin算法做了點改進，對
進制為D的字符串求值的時候為了防止溢出會模一個素數，而且不會每次都迭代求下一個子串的
值，而是從當前子串的值直接遞推出下一個字符的值。怎麼遞推了，其實很簡單，就是當前值去
掉最高位再乘以D(相當於左移一位,不過是D進制的，不能直接用<<符號)，再加上新的最低位。
   Karp-Rabin算法應該主要在於設計出合理的hash算法，比如，用取模hash函數的話，得保
證hash表足夠大，否則沖突太多，速度就不會怎麼好了。比如這個題，hash表小了就AC不了了。

   代碼如下：
#include <stdio.h>
#include <string.h>

const int MAX = 13747347;
int nHash[MAX];
char szStr[17000001];
int nN, nNC;
int nW[200];

void Insert(int nKey)
{
    int nPos = nKey;
    while (nHash[nPos] != -1 && nHash[nPos] != nKey)
    {
        nPos = (nPos + 1) % MAX;
    }
    nHash[nPos] = nKey;
}

bool Find(int nKey)
{
    int nPos = nKey;
    while (nHash[nPos] != -1 && nHash[nPos] != nKey)
    {
        nPos = (nPos + 1) % MAX;
    }
    return nHash[nPos] != -1;
}

int main()
{
    while (scanf("%d%d%s", &nN, &nNC, szStr) == 3)
    {
        memset(nW, 0, sizeof(nW));
        memset(nHash, -1, sizeof(nHash));
        int nNum = 0;
        int nSize = 0;
        for (char* pszStr = szStr; *pszStr; ++pszStr)
        {
            if (!nW[*pszStr])
            {
                nW[*pszStr] = ++nNum;
            }
            ++nSize;
        }

        int nKey = 0;
        int nAns = 0;
        int nPowN = 1;
        for (int j = 0; j < nN; ++j)
        {
            nKey = (nKey * nNC + nW[szStr[j]]) % MAX;
            nPowN *= nNC;
        }
        nPowN /= nNC;
        if (!Find(nKey))
        {
            Insert(nKey);
            nAns++;
        }
       
        for (int i = nN; i < nSize; ++i)
        {
            nKey = (nNC * (nKey - nPowN * nW[szStr[i - nN]])
                    + nW[szStr[i]]) % MAX;
            nKey = (nKey + MAX) % MAX;
           
            if (!Find(nKey))
            {
                Insert(nKey);
                nAns++;
            }
        }
       
        printf("%d\n", nAns);
    }

    return 0;
}