Rabin-Karp
比如我们要在源串 "9876543210520" 中查找 "520"，因为这些字符串中只有数字，所以我们可以使用字符集 {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'} 来表示字符串中的所有元素，并且将各个字符映射到数字 0～9，然后用 M 表示字符集中字符的总个数，这里是 10，那么我们就可以将搜索词 "520" 转化为下面的数值：
("5"的映射值 * M + "2"的映射值) * M + "0"的映射值 = (5 * 10 + 2) * 10 + 0 = 520
当然，如果“搜索词”很长，那么计算出来的这个数值就会很大，这时我们可以选一个较大的素数对其取模，用取模后的值作为“搜索词”的值。
分析一下这个数值：520，它可以代表字符串 "520"，其中:
代表字符 "5" 的部分是“ "5"的映射值 * (M 的 n - 1 次方) = 5 * (10 的 2 次方) = 500”
代表字符 "2" 的部分是“ "2"的映射值 * (M 的 n - 2 次方) = 2 * (10 的 1 次方) = 20”
代表字符 "0" 的部分是“ "0"的映射值 * (M 的 n - 3 次方) = 0 * (10 的 0 次方) = 0”
（n 代表字符串的长度）
我们可以随时减去其中一个字符的值，也可以随时添加一个字符的值。
“搜索词”计算好了，那么接下来计算“源串”，取“源串”的前 n 个字符（n 为“搜索词”的长度）"987"，按照同样的方法计算其数值：
("9"的映射值 * M + "8"的映射值) * M + "7"的映射值 = (9 * 10 + 8) * 10 + 7 = 987
然后将该值与搜索词的值进行比较即可。
比较发现 520 与 987 不相等，则说明 "520" 与 "987" 不匹配，则继续向下寻找，这时候该如何做呢？下一步应该比较 "520" 跟 "876" 了，那么我们如何利用前一步的信息呢？首先我们把 987 减去代表字符 "9" 的部分：
987 - ("9"的映射值 * (M 的 n - 1 次方)) = 987 - (9 * (10 的 2 次方)) = 987 - 900 = 87
然后再乘以 M（这里是 10），再加上 "6" 的映射值，不就成了 876 了么：
87 * M + "6"的映射值 = 87 * 10 + 6 = 876
当然了，由于采用了取模操作，当两个数值相等时，未必是真正的相等，我们需要进行一次细致的检查（再进行一次朴素的字符串比较）。若不匹配，则可以排除掉。继续下一步。
如果我们要在 ASCII 字符集范围内查找“搜索词”，由于 ASCII 字符集中有 128 个字符，那么 M 就等于 128，比如我们要在字符串 "abcdefg" 中查找 "cde"，那么我们就可以将搜索词 "cde" 转化为“("c"的码点 * M + "d"的码点) * M + "e"的码点 = (99 * 128 + 100) * 128 + 101 = 1634917”这样一个数值。
分析一下这个数值：1634917，它可以代表字符串 "cde"，其中：
代表字符 "c" 的部分是“ "c"的码点 * (M 的 n - 1 次方) = 99 * (128 的 2 次方) = 1622016”
代表字符 "d" 的部分是“ "d"的码点 * (M 的 n - 2 次方) = 100 * (128 的 1 次方) = 12800”
代表字符 "e" 的部分是“ "e"的码点 * (M 的 n - 3 次方) = 101 * (128 的 0 次方) = 101”
（n 代表字符串的长度）
我们可以随时减去其中一个字符的值，也可以随时添加一个字符的值。
“搜索词”计算好了，那么接下来计算“源串”，取“源串”的前 n 个字符（n 为“搜索词”的长度）"abc"，按照同样的方法计算其数值：
("a"的码点 * M + "b"的码点) * M + "c"的码点 = (97 * 128 + 98) * 128 + 99 = 1601891
然后将该值与“搜索词”的值进行比较即可。
比较发现 1634917 与 1601891 不相等，则说明 "cde" 与 "abc" 不匹配，则继续向下寻找，下一步应该比较 "cde" 跟 "bcd" 了，那么我们如何利用前一步的信息呢？首先去掉 "abc" 的数值中代表 a 的部分：
(1601891 - "a"的码点 * (M 的 n - 1 次方)) = (1601891 - 97 * (128 的 2 次方)) = 12643
然后再将结果乘以 M（这里是 128），再加上 "d" 的码点值不就成了 "bcd" 的值了吗：
12643 * 128 + "d"的码点 = 1618304 + 100 = 1618404
这样就可以继续比较 "cde" 和 "bcd" 是否匹配，以此类推。
如果我们要在 Unicode 字符集范围内查找“搜索词”，由于 Unicode 字符集中有 1114112 个字符，那么 M 就等于 1114112，而 Go 语言中使用 16777619 作为 M 的值，16777619 比 1114112 大（更大的 M 值可以容纳更多的字符，这是可以的），而且 16777619 是一个素数。这样就可以使用上面的方法计算 Unicode 字符串的数值了。进而可以对 Unicode 字符串进行比较了。
其实 M 可以理解为进位值，比如 10 进制就是 10，128 进制就是 128，16777619 进制就是 16777619。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN=16000005;
const int NUM=256;
int hashCode[NUM];
char str[1000000];
bool vis[MAXN];
int fast_pow(int a,int n)
{
int res=1;
while(n)
{
if(n&1) res=res*a;
a=a*a;
n>>=1;
}
return res;
}
int main()
{
int n,base,len;
memset(vis,0,sizeof(vis));
memset(hashCode,0,sizeof(hashCode));
scanf("%d%d",&n,&base);
scanf("%s",str);
if(n>=base)
{
printf("0\n");
return 0;
}
len=strlen(str);
int id=0;
for(int i=0;i<len;i++)
{
if(hashCode[str[i]]==0)
{
hashCode[str[i]]=id++;
if(id>=base) break;//所有的字符集都出现
}
}
int hashVal=0,highVal=fast_pow(base,n-1),sum=0;
for(int i=0;i<n;i++)//计算第一个长度为n的子串
{
hashVal=hashVal*base+hashCode[str[i]];
}
if(vis[hashVal]==0)
{
vis[hashVal]=1;
sum++;
}
for(int i=1;i<=len-n;i++)
{
hashVal=(hashVal-hashCode[str[i-1]]*highVal)*base+hashCode[str[i+n-1]];//去除hashVal的最高位，补上新偏移到的最低位
if(vis[hashVal]==0)
{
vis[hashVal]=1;
sum++;
}
}
printf("%d\n",sum);
return 0;
}
