poj 3461 Oulipo Rabin-Karp 字符串匹配

  裸的字符串匹配，子串最長10,000，母串最長1,000,000。
   求子串在母串中出現的次數。
   如果子串長度較小，那麼直接RK匹配即可，hash值相同時候，直接比較字符串是否相同。
但是這個題的子串太長了，還比較字符串會超時，如果不比較字符串理論上是錯誤的，雖然
出錯的概率很小，而且概率還是跟模數的選擇以及運算時候是否溢出有關。
   剛開始用了int，發現一直wa了，估計就是運算時候就超int了，取模沒起到作用。模數的選
擇能夠提高正確率。Rabin-Karp 字符串匹配雖然比較好寫，也很容易理解，但是適用情況感
覺不是很廣，比如子串太長了，處理就麻煩了，捨棄子串比較也不是很好。
   但是子串不長的話，Rabin-Karp 字符串匹配還是很不錯的。
   相比而言，這個題用kmp應該會好很多。

   代碼如下：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

typedef long long INT;
char szStrM[1000010];
char szStrS[10010];
const INT MOD = 16381 * 4733 + 1;

int main()
{
    int nT;
   
    scanf("%d", &nT);
    while (nT--)
    {
        scanf("%s%s", szStrS, szStrM);
        INT nMatch = szStrS[0] - 'A';
        INT nPowN = 1;
        int nSizeS = 1;
        char* pszStr = szStrS + 1;
        while (*pszStr)
        {
            nMatch = (26 * nMatch + *pszStr - 'A') % MOD;
            nPowN = (nPowN * 26) % MOD;
            ++nSizeS;
            ++pszStr;
        }
        //prINTf("match:%d\n", nMatch);
       
        int nSizeM = strlen(szStrM);
        INT nKey = 0;
        for (int i = 0; i < nSizeS; ++i)
        {
            nKey = (26 * nKey + szStrM[i] - 'A') % MOD;
        }
        //prINTf("key:%d\n", nKey);
       
        int nAns = 0;
        for (int i = 0; i <= nSizeM - nSizeS; ++i)
        {
            //prINTf("key:%d\n", nKey);
            if (nKey == nMatch)
               // && memcpy(szStrS, szStrM + i, nSizeS) == 0)
            {
                ++nAns;
            }
            nKey = (26 * (nKey - nPowN * (szStrM[i] - 'A')) % MOD
                    + szStrM[i + nSizeS] - 'A') % MOD;
            nKey = (nKey + MOD) % MOD;
        }
       
        printf("%d\n", nAns);
    }
   
    return 0;
}