字符串哈希（c++）

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^i
        p[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'o
        if(get(l1,r1) == get(l2,r2)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

上述笔记根据B站董晓算法记录~