• 字符串哈希可以快速判断一段字符串与另一段字符串是否相等

公式

问题

• $h[r] - h[l-1]$的时候，为什么要先把$h[l-1]$往左(往高位)移动 $p^(R-L+1)$位呢，而不直接减呢?

1. 两段所乘的$p$的指数不同，每一项都相差$r - l + 1$次
2. 用二进制数举例子，$101101$ 这个 你想求$h[3,4]$ 也就是$（11）$ 。如果用$（1011）$直接减去$（10）$ 也就是十进制的$11-2=9$，这显然不对 但是移位以后$ （10）$ 变成$（1000）$之后再减，$（1011）-（1000）=（11）$也就是是十进制的$11-8=3 $, $3$的二进制正好是$（11）$是我们想要的结果。

#include <iostream>
using namespace std;

const int N = 1e5 + 10;

typedef unsigned long long ULL;

#define P 131

ULL h[N], p[N];
char str[N];

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

int main()
{
    int n, m;
    scanf("%d%d%s", &n, &m, str + 1);
    
    p[0] = 1;
    for (int i = 1; i <= n; i ++ ) {
        h[i] = h[i - 1] * P + str[i];   // 保证h[i]不为0
        p[i] = p[i - 1] * P;    // 保证p[i]不为0
    } 
    
    int l1, r1, l2, r2;
    while (m -- )
    {
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else    puts("No");
    }
    
    return 0;
}

练习：字符串哈希