字符串哈希

字符串哈希概述

字符串哈希，是将每一位字符（的ASCII码）当做一个$P$进制的数，最后将字符串表示的$P$进制数字对$N$取模，模下来的就是我们哈希出来的数字

字符串哈希的时候，我们不考虑冲突，默认人品是足够好的，给出的方法能在$99$%+的情况下避免冲突

映射后不能为0，映射为0是一定会冲突的，A为0，那AA、AAA都会是0

$P$一般取131或者13331

$N$可以取$2 ^ {64}$，我们如果用$unsigned$ $long$ $long$ 存储数据，就不用手动取模了，溢出操作就会自动取模

最后我们可以可以把一个字符串映射为一个$unsigned$ $long$ $long$的整数

本题思路分析

比较子串是否相同，可以转化为两个子串的哈希值是否相同

在本题中，我们要知道每一个子串的哈希值。由于查询量很大，每次计算过于麻烦。可以采用前缀和预处理，达到$O(1)$的查询效率

注意，字符串的哈希值是一个$P$进制的数字

前缀和处理

h为前缀和数组，str为字符串数组，p是P每一位的权重
前缀和: $h[i] = h[i - 1] * P + str[i]$
区间和: $l$到$r$区间子串的哈希值: $h[r] - h[l - 1] * p[r - l + 1]$

区间和公式:
eg: 已知子串ABCDE 与 ABC，若要求DE哈希值，则将ABC左移两位（乘$P ^ 2$），ABCDE - ABC00 = DE，

代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef unsigned long long ULL; // 用ULL存储，溢出即取模

const int N = 100010, P = 131; // P取131

int n, m;
char str[N];
ULL h[N], p[N]; // 哈希前缀和数组和P进制每位权重的数组

ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1]; // 返回区间和
}

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s", str + 1);

    p[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        h[i] = h[i - 1] * P + str[i]; // 计算前缀和
        p[i] = p[i - 1] * P; // 计算P进制数字每一位权重
    }

    while (m -- )
    {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);

        if (get(l1, r1) == get(l2, r2)) puts("Yes"); // 利用区间和求出区间哈希值，若区间哈希值相等，则子串相等
        else puts("No");
    }

    return 0;
}