一. 题目

二. 思路

三. 代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ULL=unsigned long long;
const int N=1e5+10, S=131;

int n, m;
char str[N];

class StrHash
{
public:
    ULL head[N], sys[N];//存储1~n的哈希值，和哈希进制差值

public:
    StrHash()
    {
        initIO();
        fill(head, head+N, 0);
        fill(sys, sys+N, 0);
    }

    void initIO()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr), cout.tie(nullptr);
    }

    void makeHash()
    {
        sys[0]=1;
        for(int i=1;i<=n;++i)
        {
            sys[i]=sys[i-1]*S;
            head[i]=head[i-1]*S+str[i];
        }
    }
    //获取字符串str[l~r]的哈希值
    ULL getHash(int l, int r)
    {
        return head[r]-head[l-1]*sys[r-l+1];
    }
}sh;

int main()
{
    cin>>n>>m>>str+1;
    sh.makeHash();

    while(m--)
    {
        int l1, r1, l2, r2;
        cin>>l1>>r1>>l2>>r2;
        if(sh.getHash(l1, r1)==sh.getHash(l2, r2)) cout<<"Yes";
        else cout<<"No";
        cout<<endl;
    }
}