#P0227. 字符串哈希

字符串哈希

题目描述

给定一个长达 nn 个字符串,还包括 mm 个询问,每个询问都包含四个整数 l1r1l2r2l_1、r_1、l_2、r_2, 要求判断两个子串是否完全相同。

输入格式

第一行包含整数 nnmm,表示字符串长度和询问次数。

第二行包含一个长度为 nn 的字符串,字符串中只包含大小写英文字母和数字。

接下来 mm 行,每行包含四个整数 l1r1l2r2l_1、r_1、l_2、r_2,表示一次询问所涉及的两个区间。

输出格式

对于每个询问输出一个结果,如果两个字符串子串完全相同则输出 Yes,否则输出 No

每个结果占一行;

数据范围

1n,m1051 ≤ n, m ≤ 10^5

输入样例:

5 3
aaaab
1 2 3 4
1 3 2 4
1 1 1 2

输出样例:

Yes
Yes
No