這個(gè)題是求一個(gè)字符串里面出現(xiàn)了多少個(gè)長(zhǎng)度為N的不同子串，同時(shí)給出了母串里面不同字符
的個(gè)數(shù)NC。
保存子串到set里面直接暴力肯定超時(shí)了。這個(gè)題有個(gè)利用字符串hash的解法，雖然理論上有
bug，但是能過(guò)這個(gè)題。
利用給出的NC，對(duì)長(zhǎng)度為N的字符串，將其當(dāng)作NC進(jìn)制的數(shù)字，求出其值，對(duì)值進(jìn)行hash，
求出不同的hash位置個(gè)數(shù)。
這個(gè)算法其實(shí)類(lèi)似于Karp-Rabin字符串匹配算法。不過(guò)，Karp-Rabin算法做了點(diǎn)改進(jìn)，對(duì)
進(jìn)制為D的字符串求值的時(shí)候?yàn)榱朔乐挂绯鰰?huì)模一個(gè)素?cái)?shù)，而且不會(huì)每次都迭代求下一個(gè)子串的
值，而是從當(dāng)前子串的值直接遞推出下一個(gè)字符的值。怎么遞推了，其實(shí)很簡(jiǎn)單，就是當(dāng)前值去
掉最高位再乘以D(相當(dāng)于左移一位,不過(guò)是D進(jìn)制的，不能直接用<<符號(hào))，再加上新的最低位。
Karp-Rabin算法應(yīng)該主要在于設(shè)計(jì)出合理的hash算法，比如，用取模hash函數(shù)的話(huà)，得保
證hash表足夠大，否則沖突太多，速度就不會(huì)怎么好了。比如這個(gè)題，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;
}