207. 字符串哈希
时间限制：1000 MS 内存限制：64 MB
题目描述
# 字符串哈希 ## 题目描述 给定一个长度为 $n$ 的字符串 $s$，再给定 $m$ 个询问。每个询问包含四个整数 $l_1,r_1,l_2,r_2$，请判断子串 $s[l_1..r_1]$ 与 $s[l_2..r_2]$ 是否完全相同。 两个子串完全相同，当且仅当它们长度相同，且对应位置的字符均相同。 字符串只包含大小写英文字母和数字，字符比较区分大小写。字符串的位置从 $1$ 开始编号，所有区间均包含左右端点。 ## 输入格式 从文件 `hashs.in` 读入数据。 第一行包含两个整数 $n,m$，分别表示字符串的长度和询问次数。 第二行包含一个长度为 $n$ 的字符串 $s$。 接下来 $m$ 行，每行包含四个整数 $l_1,r_1,l_2,r_2$，表示一次询问涉及的两个子串区间。 ## 输出格式 将结果输出到文件 `hashs.out`。 对于每个询问，输出一行：如果两个子串完全相同，输出 `Yes`；否则输出 `No`。输出的大小写必须与上述要求一致。 ## 数据范围 - $1 \le n,m \le 10^5$。 - $1 \le l_1 \le r_1 \le n$。 - $1 \le l_2 \le r_2 \le n$。 - 字符串 $s$ 只包含大小写英文字母和数字，区分大小写。 ## 样例输入 ``` 8 3 aabbaabb 1 3 5 7 1 3 6 8 1 2 1 2 ``` ## 样例输出 ``` Yes No Yes ``` ## 运行限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$64$ MB。