子串相等查询

题目描述

给定一个只包含小写英文字母的字符串 s，需要回答 q 次询问。

每次询问给出 l1、r1、l2、r2，请判断子串 s[l1..r1] 与 s[l2..r2] 是否完全相同。

字符串下标从 1 开始。

可以使用前缀字符串哈希实现。为了降低碰撞风险，建议使用双哈希或其他可靠方法。

输入格式

第一行一个字符串 s。

第二行一个整数 q。

接下来 q 行，每行四个整数 l1、r1、l2、r2。

输出格式

每次询问输出一行：

• 两个子串相同，输出 Yes；
• 否则输出 No。

abcabc
4
1 3 4 6
1 2 2 3
2 5 2 5
1 3 1 2

Yes
No
Yes
No

数据范围

• 1 <= |s| <= 200000
• 1 <= q <= 100000
• 1 <= l1 <= r1 <= |s|
• 1 <= l2 <= r2 <= |s|