mikhail_dvorkin icon

Polynomial hashing in Python

mikhail_dvorkin | PRO | 04/30/20 10:33:59 AM UTC | 0 ⭐ | 1397 👁️ | Never ⏰ | []
Python |

620 B

|

None

|

0 👍

/

0 👎

# 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