题目描述

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

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

输入格式
第一行包含整数 n 和 m，表示字符串长度和询问次数。

第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。

接下来 m 行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。

注意，字符串的位置从 1 开始编号。

输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

每个结果占一行。

数据范围
1≤n,m≤105
输入样例：
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出样例：
Yes
No
Yes

算法 字符串哈希

1.首先求出所有字符串前缀的哈希值求出来
2.然后用公式分别算出两个给定区间的哈希值
3.由于这两个数都是属于（0,2^64-1）之间的数，如果这两个数相同，那就说明这两个字符串
相同，如果这两个哈希值不同，那就说明这两个字符串不同

参考文献

y总

C++ 代码

#include  <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//字符串哈希是模2^64的，因为long long的大小正好是这个，所以直接用longlong来。
//也就是说，这里的溢出等价于取模运算。
typedef unsigned long long ULL;
//N数据范围       P：P进制，一般取131或者13331
const int N = 100010 , P = 131;
//n字符串的长度  m询问的次数
int n , m;
//str字符串
char str[N];
//h哈希表       p存储p的多少次方（公式里面有乘以一个P次方的）
ULL h[N] , p[N];

//获取字符串哈希值的函数
ULL get(int l , int r){
    //公式，图解里面有
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main(){
    //输入
    scanf("%d%d%s" , &n , &m , str + 1);
    //p的0次方为1 
    p[0] = 1;
    //从第一个字母开始
    for(int i = 1 ; i <= n; i++){
        //初始化p一直到多少次方，跟字符串长度有关
        p[i] = p[i - 1] * P;
        //初始化哈希表，也就是求出所有的字符串前缀哈希值.str[i]转化成ASCII码值参与运算
        h[i] = h[i - 1] * P + str[i] ;
    }

    //m个询问
    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;
}