A56 - String Hash

提出

TLE

code: python

n, q = map(int, input().split())

s = input()

for query in abcd:

a, b, c, d = query0, query1, query2, query3,

print("Yes")

else:

print("No")

解答

code:python

N, Q = map(int, input().split())

S = input()

# 文字を数値に変換

# ord(c) で文字 c の文字コード（ASCII コード）を取得

T = list(map(lambda c: ord(c) - ord('a') + 1, S))

# 100 の n 乗を前計算

MOD = 2147483647 # 適当な素数

power100 = None * (N + 1)

power1000 = 1

for i in range(N):

power100i + 1 = power100i * 100 % MOD

# H1, H2, ..., HN を計算する

# H1: S1,1, H2: S1.2, H3: S1,3

H = None * (N + 1)

H0 = 0

for i in range(N):

Hi + 1 = (Hi * 100 + Ti) % MOD

# ハッシュ値を求める関数

# Sl:r のハッシュ値は (Hr - power100r - l + 1 * Hl - 1) % MOD で計算

# C++ とは異なり、（負の値）% M (M >= 1) も 0 以上 M-1 以下になることに注意

def hash_value(l, r):

return (Hr - power100r - l + 1 * Hl - 1) % MOD

for a, b, c, d in queries:

hash1 = hash_value(a, b)

hash2 = hash_value(c, d)

if hash1 == hash2:

print("Yes")

else:

print("No")