$\color{green}{<–画图不易，点下这里赞一下吧}$

题目解析：

• 给出一个字符串，例如 s = "adcdabcde"
• 给出[l1, r1]，[l2, r2]
• 问字符串的子串 s[l1, r1] s[l2, r2] 是否相同

解题思路：

• 思路一：暴力，超时。

• 思路二：字符串哈希

将字符串转换成一个P进制的数字，例如 131 进制的数字。这个值看做字符串的哈希值h。

相同的字符对应的P进制数字一定相同，即哈希值相同。

因为进制取得131，认为哈希值相同的字符是相等的。

因此，只要能快速求出s[l1, r1] 和 s[l2,r2]对应的字符串的哈希值h[s[l1, r1]] h[s[l2, r2]]，并判断是否相等。就能得出l1, r1 l2,r2对应的字符串是否相同

具体算法

如何快速求出s[l, r]的哈希值h[s[l,r ]]是关键。这里可以使用前缀和思想。

字符串s的下标从1开始，字符串长度为n。P 取131。字符串s[1, t]对应的哈希值记为h[t]。

1. 分别求出 h[1], h[2], h[3],h[n]

2. 此时 h[s[l, r]] = h[r] - h[s[l - 1]] * pow(131, r - l + 1)

为什么？举个例子

例如s = "abcabcd", 各个位置对应的数字为： s = "97 98 99 97 98 99 100"

h[1] = 97
h[2] = h[1] * P + h['b'] = 97 * 131 + 98 = 12,805
h[3] = h[2] * P + h['c'] = 12805*131 + 99 = 1,677,554
h[4] = h[3] * P + h['a'] = 1,677,554 * 131 + 97 = 219,759,671‬
h[5] = h[4] * P + h['b'] = 219,759,671‬ * 131 + 98 =28,788,516,999‬
h[6] = h[5] * P + h['c'] = 28,788,516,999‬ * 131 + 99 = 3,771,295,726,968
h[7] = h[6] * P + h['d'] = 3,771,295,726,968 * 131 + 100 = 494,039,740,232,908‬

求 h[s[2, 3]]

• h[3] = h['abc'] = h['a'] * pow(P, 2) + h['b'] * pow(P, 1) + h['c'] = 1,677,554

• h[1] = h['a'] = 97

• h[s[2, 3]] = h['bc'] = h['b'] * pow(P, 1) + h['c']

• 所以：h[s[2, 3]]= h[3] - h[1] * pow(P, 2) = 12,937‬

• 也就是：h[s[l, r]] = h[r] - h[l - 1] * pow(P, r - l + 1)

再举个例子

以s为数字字符串，各个位置的值等于数字本身，P等于10，说明h[s[l, r]] = h[r] - h[s[l - 1]] * pow(P, r - l + 1)

s = '4564'

h[1] = 4
h[2] = 45
h[3] = 456
h[4] = 4565
h[s[2,3]] = 456 - 4 * 100 = h[3] - h[1] * pow(10, 2)

代码：

import sys
n, m = map(int, sys.stdin.readline().split())
P = 131
s = input()
Q = 1 << 64
h = [0] * (len(s) +  10)
p = [0] * (len(s) +  10)
p[0] = 1
s = " " + s
# 根据公式求
def get(l, r):
    return (h[r] - h[l - 1] * p[r - l + 1]) % Q

# 初始化
for i in range(1, len(s)):
    h[i] = (h[i - 1] * P + ord(s[i])) % Q
    p[i] = p[i - 1] * P % Q

while m:
    m -= 1
    l1, r1, l2, r2 = map(int, input().split())
    if get(l1, r1) == get(l2, r2):
        print("Yes")
    else:
        print("No")