摘要
Title: 841. 字符串哈希
Tag: 字符串哈希
Memory Limit: 64 MB
Time Limit: 1000 ms

841. 字符串哈希

题意

给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。

思路

字符串哈希板子题

注意的点：

P为经验值，可以取131，也可以取13331
对 $2^{64}$ 进行取模，一定要模全了！！！
别忘了对 $p[0]$ 进行赋值为1，因为 $p^0 = 1$
s = " " + s，字符串的第0位空出来
区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样，只差两位，乘上 $P^2$ , 把 ABC 变为 ABC00，再用 ABCDE - ABC00 得到 DE 的哈希值。

代码

'''
Author: NEFU AB-IN
Date: 2022-02-12 16:07:23
FilePath: \ACM\Acwing\841.py
LastEditTime: 2022-02-12 16:12:41
'''

N = int(1e5 + 100)
P, MOD = 131, 1 << 64

h = [0] * N
p = [0] * N

p[0] = 1 #初始化


def get(l, r):
    return (h[r] - h[l - 1] * p[r - l + 1] % MOD) % MOD


if __name__ == "__main__":
    n, m = map(int, input().split())
    s = input()

    s = " " + s #空一位

    for i in range(1, n + 1):
        p[i] = p[i - 1] * P % MOD
        h[i] = (h[i - 1] * P % MOD + ord(s[i])) % MOD

    for i in range(m):
        l1, r1, l2, r2 = map(int, input().split())

        if get(l1, r1) == get(l2, r2):
            print("Yes")
        else:
            print("No")