# zabcd
# abcdz
# → 4
# hash(abcdz) = (a * X**4 + b * X**3 + c * X**2 + d * X**1 + z * X**0) % M
# a * X**1 + b * X**0
# a * X**3 + b * X**2 + c * X**1 + d
def polyhash(start, end):
return (p[end] - p[start] * z[end - start]) % M
s = input()
t = input()
n = len(s)
text = s + t + t # zabcd abcdz abcdz
M = 1_000_000_007
X = 566_239
z = [1]
p = [0]
for c in text:
z.append(z[-1] * X % M)
p.append((p[-1] * X + ord(c)) % M)
hash_of_s = p[n] # polyhash(0, n) # Andrew's hack
for i in range(n):
if hash_of_s == polyhash(n + i, 2 * n + i):
print(i)
exit()
print(-1)
Comments