题目描述
给定一个长度为n的字符串，再给定m个询问，每个询问包含四个整数$l_1,r_1,l_2,r_2$，请你判断[$l_1,r_1$]和[$l_2,r_2$]这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数n和m，表示字符串长度和询问次数。
第二行包含一个长度为n的字符串，字符串中只包含大小写英文字母和数字。
接下来m行，每行包含四个整数$l_1,r_1,l_2,r_2$，表示一次询问所涉及的两个区间。
注意，字符串的位置从1开始编号。
输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出“Yes”，否则输出“No”。
每个结果占一行。
数据范围
$1 \leq n,m \leq 10^5$
输入样例:
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出样例:
Yes
No
Yes
算法1
(字符串哈希) $O(n)+O(m)$
全称字符串前缀哈希法，把字符串变成一个p进制数字（哈希值），实现不同的字符串映射到不同的数字。
对形如 $X_1X_2X_3\cdots X_{n-1}X_n$ 的字符串,采用字符的ascii 码乘上 P 的次方来计算哈希值。
映射公式 $(X_1 \times P^{n-1} + X_2 \times P^{n-2} + \cdots + X_{n-1} \times P^1 + X_n \times P^0) \bmod Q$
注意点：
1. 任意字符不可以映射成0，否则会出现不同的字符串都映射成0的情况，比如A,AA,AAA皆为0
2. 冲突问题：通过巧妙设置P (131 或 13331) , Q $(2^{64})$的值，一般可以理解为不产生冲突。
问题是比较不同区间的子串是否相同，就转化为对应的哈希值是否相同。
求一个字符串的哈希值就相当于求前缀和，求一个字符串的子串哈希值就相当于求部分和。
前缀和公式 $h[i+1] = h[i] \times P + s[i]$ $i \in [0,n-1]$ h为前缀和数组，s为字符串数组
区间和公式 $h[l,r] = h[r] - h[l-1] \times P^{r-l+1}$
区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样，只差两位，
乘上 $P^2$ 把 ABC 变为 ABC00，再用 ABCDE - ABC00 得到 DE 的哈希值。
C++ 代码
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e5+5,P = 131;//131 13331
ULL h[N],p[N];
// h[i]前i个字符的hash值
// 字符串变成一个p进制数字，体现了字符+顺序，需要确保不同的字符串对应不同的数字
// P = 131 或 13331 Q=2^64，在99%的情况下不会出现冲突
// 使用场景： 两个字符串的子串是否相同
ULL query(int l,int r){
return h[r] - h[l-1]*p[r-l+1];
}
int main(){
int n,m;
cin>>n>>m;
string x;
cin>>x;
//字符串从1开始编号，h[1]为前一个字符的哈希值
p[0] = 1;
h[0] = 0;
for(int i=0;i<n;i++){
p[i+1] = p[i]*P;
h[i+1] = h[i]*P +x[i]; //前缀和求整个字符串的哈希值
}
while(m--){
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
if(query(l1,r1) == query(l2,r2)) printf("Yes\n");
else printf("No\n");
}
return 0;
}
区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样，只差两位，
乘上P的二次方把 ABC 变为 ABC00，再用 ABCDE - ABC00 得到 DE 的哈希值。
说实话y总这段讲得有点不清楚。看了几遍都没完全懂。你这个解释特别好！一下就懂了！
这个就是解释的Y总讲的左移的那一部分吗
对的！
tql 兄弟 听君一席话胜读十年书属于是了
谢谢你超人
其实这段和普通二进制是一样的
这里简直就是点睛之笔！！！
谢谢你，我也是看了这个就反应过来了，给你花花❀
就是补后缀0嘛，还好吧。
谢谢你！超人
真的是太可以了！
y总默认我们已经知道了
你简直就是超人
自己给自己写的第一篇题解 点赞评论！！
hh
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
加上当前位置字符的ASCII码，就是一个计算P进制的过程 自己模拟一下会更明白~
假设字符串为“123”，那h[2]=(1p^2+2p^1+3p^0) 又等于h[1]p+s[2] 即 (1p^1+2p^0)p+3
这里的123其实实际上不是数字，是用它的ASSIC码计算，为了方便理解才直接用数字
那公式解释的非常棒，一直没理解是怎么回事情
牛！
ull存hash值爆了相当于自动取模可以理解，但是p数组存每一位权值也会爆啊，难道是因为（x+y）%z＝（x%z+y%z）%z这种的吗
比如p【100】的时候相当于存了第100位的权值也就是131^99肯定大于ull_max了，存放权值的数组爆了之后存进ull的数组不影响吗
在括号里面相加取模和括号里面每个元素分别取模没区别
get返回值是ull类型，如果p[]过大会取模，这里先取模了
用到p[i]的地方就只有h[r] - h[l-1]*p[r-l+1]这里：
参照(ab)%p=(a%p * b%p)%p
可得(h[l-1]%Q)(p[r-l+1]%Q)= (h[l-1]*p[r-l+1])%Q
而又参照(a+b)%p=(a%p+b%p)%p
可得h[r]%Q-(h[l-1]p[r-l+1])%Q = (h[r] - h[l-1]p[r-l+1])%Q
(h[r] - h[l-1]*p[r-l+1])%Q符合题意
太强了 我懂了 非常感谢
p[i+1] = p[i]*P;
这个地方不会爆 long long 吗
可以爆，但是就是爆了也没关系，反正都是要取模的，爆了的过程就是取模的过程
爆了相当于取模嘛，爆了不是会变成一个负数嘛？有点不太理解这里
unsigned没有负数从0开始，所有相当于他的区间是一个和，最大的溢出了就回到0了，相当于取模
哦哦
为什么爆了取模没关系呢？
或者说为什么爆了就相当于取模？
（爆了相当于取模）哈希值判断，如果取模之后的值不相同，则字串必定不相同；相对的，如果取模后值相同，则需要更加细致的比较字串。 也就是说，这种方法提高了不相同的字串之间的比较效率，但是对相同字串的比较效率提高不明显
同时一般来说，在题目给的数据范围内，已经挑选好P 和 Q的情况下，不太容易出现取模后值相等而字串不同的情况
X1^2 下标和指数是怎么打出来的呀
latex公式编辑器了解一下
这里get里面的l - 1啥意思，一直不理解
因为l那个位置是我们要考虑的，所以是l-1,跟差分一样的
这个p数组是干嘛的呀
求p的多少次方用的，比如p[i]就是p的i次方
相当于将p[r - l + 1]相当于将原数组左移r - l + 1位，p可以理解为p进制的数。
请问为何超范围就相当于是对2^64次方取模了?
ull是2^64
unsigned long long 数据范围 [0, 2^ 64],爆了数据访问就会回到0。而有符号的long long爆了会是一个负数，没有取模的效果。
int的范围是多少呀？32次方嘛？那long int和int一样还是和long long int一样？
说一个细思极恐的事。h[i+1] = h[i]*P +x[i]，为什么下一个的模值可以用上一个的模值来计算。这样说：A%7 + B%7 == (A+B)%7?, A= 10, B = 3的话会相等吗？平时计算A+B模7都是先算A+B，再取模。其实文中是可以用上一个模值求下一个模值这么做的，HH，但是不推导出来会自我怀疑这为什么是对的。
模运算结合律
10%7=3,3%7=3,3+3=6 而(13)%7=6,有啥问题吗。。
A=7x+a,B=7y+b,A+B=7(x+y)+a+b
(A+B)%7=a+b,A%7=a,B%7=b
A%7+B%7=a+b
tql
写的真的很好！很严谨，都讲明白了！
为什么那个p数组改成用cmath里面的pow函数就会出错啊，求大佬解答
注意n的范围，n<=1e5。pow(i,n)是计算i的n次方的函数，其中i和n都可以是整数或浮点数。n的取值范围一般是[-2^31,2^31-1]。
int h[N],p[N}也能过..
关于区间对齐的理解：
有两个字符串：ABCDE 和 ABC。这两个字符串的前三个字符相同，只有后两位不同。
接下来，提到乘上P的二次方，即将ABC变为ABC00。这里的P可能是一个代表进制的数字，比如P=10代表十进制，P=2代表二进制。乘上P的二次方表示在ABC后面添加两个零。例如，如果P=10，那么ABC变为ABC00。
然后，将扩展后的ABC00从原始字符串ABCDE中减去。这可能涉及将字符串ABCDE转换为数字，然后执行减法运算。这个过程产生的结果是DE。
最后，DE被描述为一个哈希值。这可能涉及对DE进行某种哈希函数的操作，以生成一个表示DE内容的固定长度的字符串。
综合起来，这个过程可以被理解为通过在字符串的末尾添加零，然后计算差异（ABCDE - ABC00），最终得到一个哈希值。其中，P的二次方可能用于确保字符串长度一致。请注意，具体的实现取决于所使用的编程语言和哈希函数。
妙啊