题目描述

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

形象算法

这个字符串哈希比较形象了
假设大家已经知道字符串哈希是什么了

大概思路是这样的，举个例子,设字符串s下标从1开始(因为处理前缀和要用到0)

字符串太抽象了我们拿一个数字举例子吧

字符串是这样的（中间没有空格）：1 2 3 9 9 1 2 3
下标是这样的： 1 2 3 4 5 6 7 8
那么我们这个字符串的哈希可以这么设计：
如果把这个字符串看成一个p进制数字
第i位的哈希值=s[i]*P^i
这个字符串的哈希值就可以表示为 1xP^1+2xP^2+3xP^3+9xP^4+9xP^5+1xP^6+2xP^7+3xP^8
然后像正常的数字处理前缀和一样求出前缀和

在查询的时候假如我们要查询区间[1,3],[6,8]（这俩相等的）
1.首先我们求出区间和sum(1,3),sum(6,8)（和前缀和求法一样）
2.接着（关键）左边的区间需要向右移动五个单位才能和右边的区间重合
那么不就相当于，把区间[1，3]的每一个字符向右移动五个单位
那么就像乘法一样每个字符都要乘p^5，那么显然[1,3]的字符串乘p^5就到了[6，8]这个位置
然后判断两个区间和是否相同就行了

讲完了，具体实现看代码

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
const int P=131,N=1e5+7;
char s[N];
unsigned long long sum[N],pw[N];//sum[i]代表前i位的字符串哈希前缀和，pw[i]代表P的i次方
int n,q,l,r,u,v;
bool same(int l,int r,int u,int v)
{
    if(v<r)//保证r<=v
        swap(l,u),swap(r,v);
    return sum[v]-sum[u-1]==(sum[r]-sum[l-1])*pw[v-r];
}
int main()
{
    cin>>n>>q;
    cin>>(s+1);
    n=strlen(s+1);
    pw[0]=1;
    for(int i=1;i<=n;i++)
    {
        pw[i]=pw[i-1]*P;
        sum[i]=sum[i-1]+s[i]*pw[i];
    }
    while(q--)
    {
        cin>>l>>r>>u>>v;
        printf("%s\n",same(l,r,u,v)?"Yes":"No");
    }
}