裸的字符串匹配，子串最長10,000，母串最長
1,000,000。
求子串在母串中出現(xiàn)的次數(shù)。
如果子串長度較小，那么直接RK匹配即可，hash值相同時(shí)候，直接比較字符串是否相同。
但是這個(gè)題的子串太長了，還比較字符串會(huì)超時(shí)，如果不比較字符串理論上是錯(cuò)誤的，雖然
出錯(cuò)的概率很小，而且概率還是跟模數(shù)的選擇以及運(yùn)算時(shí)候是否溢出有關(guān)。
剛開始用了int，發(fā)現(xiàn)一直wa了，估計(jì)就是運(yùn)算時(shí)候就超int了，取模沒起到作用。模數(shù)的選
擇能夠提高正確率。Rabin-Karp 字符串匹配雖然比較好寫，也很容易理解，但是適用情況感
覺不是很廣，比如子串太長了，處理就麻煩了，舍棄子串比較也不是很好。
但是子串不長的話，Rabin-Karp 字符串匹配還是很不錯(cuò)的。
相比而言，這個(gè)題用kmp應(yīng)該會(huì)好很多。
代碼如下：
#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;
}