1、定义
字符串哈希把不同的字符串映射成不同的整数
1.1、规则
1、把字符串映射成一个P进制数字
对于一个长度为n的字符串s
这样定义Hash函数:
例如:字符串abc,其哈希函数值为ap^2 + bp^1 + c;
即97 * 131^2 + 98 * 131^1 + 99;
2、两个字符串不一样,hash函数值却是一样,这样的现象叫哈希碰撞(冲突)
3、哈希碰撞的方法:
巧妙设置P和M的值,保证P与M互质。
P通常取质数131或13331
M通常取大整数2^64,把哈希函数值h定义为ULL,超过则自动溢出,等价于取模。因为ULL的上界就是2 ^ 64
2、实现
这里说一下区间和这个公式:
可以看到整个公式可以理解为将h[3] *p^2正好是把第三项的前缀和平方,这样拿第5项前缀和 - 第三项前缀和 正好就等于DE
也可以看成是ABCDE - ABC00这样。
代码模板:
3、例题841. 字符串哈希 - AcWing题库
AC代码:
#include<iostream>
#include<cstring>using namespace std;typedef unsigned long long ULL;
const int N = 1e5+10,P = 131;
ULL h[N],p[N];//h[]存映射值,p[]存P进制的值
int n,m;
char s[N];
//计算1~i的哈希值
ULL get(int l,int r)
{return h[r] - h[l-1] * p[r-l+1];
}int main()
{scanf("%d %d%s", &n, &m,s+1);h[0] = 0,p[0] = 1;//预处理哈希值的前缀和for(int i=1;i<=n;i++){//p[i] = P^ip[i] = p[i-1] * P;//求一下P进制h[i] = h[i-1] * P + s[i];//求出前缀和下的哈希值}while (m -- ){int l1,r1,l2,r2;scanf("%d %d %d %d",&l1,&r1,&l2,&r2);//判断两个子串是否xiang'oif(get(l1,r1) == get(l2,r2)) printf("Yes\n");else printf("No\n");}return 0;
}
上述笔记根据B站董晓算法记录~