← 返回题目列表

AtCoder · tessoku_book_bd

A56. 字符串哈希

中文机器翻译题面 查看原题

配点: 1000 点

問題文

长度 小于或等于 N 的字符串 S 。下面 请回答 Q 请处理一个查询。

  • i 第查询:S[a_i, b_i] 和 按字典顺序比较 S[c_i, d_i] 匹配吗?

但是, 运算前设定中包含的S[l, r] 是 您也可以写 S 可以得到第 l 从第一个字符开始 r 指直至字符的连续子串。

制約

  • N, Q, a_i, b_i, c_i, d_i 是一个整数
  • S 是一串小写字母
  • 1 \leq N \leq 200000
  • 1 \leq Q \leq 200000
  • |S| = N
  • 1 \leq a_i \leq b_i \leq N
  • 1 \leq c_i \leq d_i \leq N
  • b_i - a_i = d_i - c_i

入力

输入是按以下格式从标准输入给出的。

N Q
S
a_1 b_1 c_1 d_1
a_2 b_2 c_2 d_2
\vdots
a_Q b_Q c_Q d_Q

出力

Q 行。 在i 行中,i 如果字符串在查询中匹配 Yes,否则 在第 No 。


入力例 1

7 3
abcbabc
1 3 5 7
1 5 2 6
1 2 6 7

出力例 1

Yes
No
No

1 个查询中, 有人问您S[1, 3] 和 按字典顺序比较 S[5, 7] 是否匹配。两者都 abc 和匹配,所以 输出Yes 。

2 个查询中, 有人问您S[1, 5] 和 按字典顺序比较 S[2, 6] 是否匹配。S[1, 5] = abcba、S[2, 6] = bcbab 和不匹配,所以No 。