题目描述

给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

映射方式

将字符串当作P进制的多位数处理，每一位的值取字符ASCII码，再对一个大整数取模。

通常为了减少哈希冲突，P 取131 或 13331， mod取 2^64。
我们可以直接用unsigned long long 来储存哈希值，就节省了取模操作。

字串的哈希值公式：value(str[l,r]) = s[r] - s[l] * p^(r - l + 1);
这里要注意我们存值的时候是从str[0]开始存储的，也就是说str[0]是p进制多位数的最高位

例如字符串为“52413”,采用P = 10来映射。从idx = 0开始读的话，得到的实际哈希值对应的数为52413，越早读入的字符对应的数位越高。当我们想求字串[2,4]对应的的哈希值时，公式为：5241 - 5 * 10^（4 - （2 - 1）） = 241，则对应了公式中的s[r] - s[l] * p^(r - l + 1);

C++ code

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ULL;

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

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

ULL get(int l,int r){
    return s[r] - s[l - 1]*p[r - l + 1]//重点注意理解公式
}

int main()
{
    cin >> n >> m >> str + 1;
    p[0] = 1;
    for(int i = 1; i <= n ; ++i){
        p[i] = p[i - 1]* P;//预处理p的i次幂
        s[i] = s[i - 1]* P + str[i];
    }

    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;
}