字符串哈希

用途

可以利用前缀和字符串哈希，可以快速判断两个区间内的字串是否相等。

例题

解析

字符串哈希原理

• 字符串哈希就是将每个子串看成P进制的数，比较两个字串是否相等，就比较两个字串所代表的数是否相等。
• 举例说明：
  比如ABCDE，按照正常的书写逻辑，左边是高位，右边是低位。这是个P进制的，假设A映射为数字1，B映射为数字2，其他的同理（这里不能映射为0，因为A，AA这样的就一样了，分不开字符串了）。那ABCDE所代表的P进制数是（1xP^4^+ 2xP^3^ + 3xP^2^ + 4xP^1^ + 5xP^0^)，这个其实就是和普通的数字表示一样，比如说642，是不是就是（6x10^2^ + 4x10^1^ + 2x10^0^)
• 这里我们将 char 类型的字符复制到 int 类型的数组里面，自动存的这个字符的ASCII码，也就是相当于将每个字符映射为其所对应的ASCII码。

前缀和字符串哈希原理

• 这里和普通的前缀和的原理差不多，只是略有不同。
• 可以利用前缀和字符哈希，求出任意字串的哈希值。
• 公式
  
• 公式推导
  h数组就是前缀和数组，h[i]代表着第0位到第i位的字符串的哈希值，如果要求l到r的哈希值，这里和普通的前缀和略有区别，这里涉及到进位问题。就是ABCDE-AB != CDE，把它看成正常的数字，只是个普通的P进制数字，那么这里应该是ABCDE-AB000 = CDE，类似于6893 - 68 != 93只有 6893 - 68 x 100 = 93 。这里向左移动的时候是乘机制，移动一位乘一个进制。这里差的位数就是l到r的位数，也就是 l - r + 1 位。

源代码

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ULL;

const int N = 1e5 + 10, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];

int get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    cin >> n >> m;
    cin >> 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;
    }

    while(m -- )
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if (get(l1, r1) == get(l2, r2)) cout << "Yes" << '\n';
        else cout << "No" << '\n';
    }

    return 0;

}