AcWing 841. 字符串哈希
原题链接
简单
作者:
kugua
,
2020-07-22 16:08:20
,
所有人可见
,
阅读 578
def get(l,r):
return (h[r]-h[l-1]*p[r-l+1])%Q
N = 100010
p = [0]*N
h = [0]*N
P = 131
Q = 2**64
p[0] = 1
n,m = map(int,input().split())
string = ' '+str(input())
#注意这里不能加.split(),否则输入进来的结果是 ['UJn6IUJn6I']
#实际我们需要的是 UJn6IUJn6I(注意前面有个空格)
print(string)
for i in range(1,n+1):#注意这里
p[i] = (p[i-1]*P)%Q
h[i] = (h[i-1]*P+ord(string[i]))%Q
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')