题目描述

给定一个长度为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

字符串哈希，我们把一串字符串看成一个p进制的数字，一般来说p取131或者13331是比较好的，首先预处理两个数组p[],h[],其中p[x]表示pd的x次幂，h[x]表示前x项的哈希值,那么我们便可以使用几乎o(1)的时间复杂度来判断两端字符串是不是相等，只需要判断两段字符串的哈希值是否相等就可以了，图片为y总求任意一段区间哈希值的公式

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int P=131;
typedef unsigned long long ull;
const int N=100010;
char str[N];
int h[N],p[N];
ull get(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
    cin>>n>>m;
   scanf("%s",str+1);
    p[0]=1;
    for(int i=1;i<=n;i++)
    {
        p[i]=p[i-1]*P;
        h[i]=h[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))cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}