Advertisement
mikhail_dvorkin

Polynomial hashing in Python

Apr 30th, 2020
913
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.62 KB | None | 0 0
  1. # zabcd
  2. # abcdz
  3. # → 4
  4. # hash(abcdz) = (a * X**4 + b * X**3 + c * X**2 + d * X**1 + z * X**0) % M
  5. # a * X**1 + b * X**0
  6. # a * X**3 + b * X**2 + c * X**1 + d
  7.  
  8. def polyhash(start, end):
  9.     return (p[end] - p[start] * z[end - start]) % M
  10.  
  11. s = input()
  12. t = input()
  13.  
  14. n = len(s)
  15. text = s + t + t # zabcd abcdz abcdz
  16. M = 1_000_000_007
  17. X = 566_239
  18.  
  19. z = [1]
  20. p = [0]
  21. for c in text:
  22.     z.append(z[-1] * X % M)
  23.     p.append((p[-1] * X + ord(c)) % M)
  24.  
  25. hash_of_s = p[n] # polyhash(0, n) # Andrew's hack
  26. for i in range(n):
  27.     if hash_of_s == polyhash(n + i, 2 * n + i):
  28.         print(i)
  29.         exit()
  30. print(-1)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement