题目描述

给定一个字符串，再给定m个询问，要求输出每一次询问中[l1, r1] 和[l2, r2] 这两个区间内的字符串是否相同；

样例

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

Yes
No
Yes

算法1

字符串哈希

字符串哈希即将一个字符串转化成一个整数，并保证字符串不同,得到的哈希值不同，这样就可以用来判断一个该字串是否重复出现过。构造哈希函数的关键点在于使不同字符串的哈希冲突率尽可能小。字符串哈希中也有用到前缀和思想；
字符串哈希与普通哈希的区别是 没有解决冲突的函数，是否冲突基本看脸
字符串哈希函数常用的有：
1. 自然溢出法：
p一般取值为131或13331；

Hash[i] = Hash[i-1]*p + str[i];

利用unsigned long long 自然溢出,相当于自动对2^64−1取模；
2. 单哈希法：

Hash[i] = (Hash[i-1]*p + str[i])%mod；

p,mod均为质数，p < mod,p，mod取尽量大时冲突很小
3. 双哈希法：
将字符串用不同mod单哈希两次，结果用二元组表示

Hash1[i] = (Hash1[i-1]*p + str[i])%mod1
Hash2[i] = (Hash2[i-1]*p + str[i])%mod2
Hash[i]:<Hash1[i],Hash2[i]>

这种方法很安全

C++ 代码

#include<iostream>
using namespace std;

typedef unsigned long long ULL;

const int N = 1e5+7, P = 131;
ULL h[N], p[N];
//h[]为字符串哈希数组；p[]为P的n次方预处理数组；

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

int main()
{
    ios::sync_with_stdio(false);

    int n, m;
    string s;
    cin>>n>>m>>s;
    p[0] = 1;           //P^0 = 1;
    for(int i = 0; i < s.size(); ++i){
        p[i+1] = p[i] * P;
        h[i+1] = h[i] * P + s[i];
    }
    int l1, r1, l2, r2;
    while(m--){
        cin>>l1>>r1>>l2>>r2;
        cout<<(get(l1, r1) == get(l2, r2) ? "Yes" : "No")<<endl;
    }
    return 0;
}