字符串哈希

最关键的就是求hash值的部分，因为高位在左，低位在右
所以 hashvalue = h[r] - h[l - 1]*p[r- l + 1];
那个数字举例
12312
l1 = 1,r1 = 2
l2 = 4,r2 = 5;

h[1] = 1,h[2] = 12
h[4] = 1231,h[5] = 12312

这样子一下子就看懂了，要高位对齐

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;

int n , m;

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

char s[N];
int main(){
    int n , m;
    cin >> n >> m;
    cin >> s + 1;
    p[0] = 1;
    for(int i = 1;i <= n;++i){
        h[i] = h[i - 1] * P + s[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" <<endl;
        else cout << "No" <<endl;
    }
    return 0;
}