Home>

### python : How to speed up polynomial hash calculation

Computing a polynomial hash on the string s. My solution (Horner's method):

``````base= int(input())
mod= int(input())
s= input()
first_expr= ord(s) * base + ord(s)
for i in range(2, len(s)):
first_expr= first_expr * base + ord(s[i])
print(first_expr % mod)
# 123 |
# 100003 |=&gt; 6080
# hash |
``````

How can I speed up this solution?

Give a link to the testing system.

Stanislav Volodarskiy2022-01-30 07:40:57

Module (`%`) must be called in a loop. Your algorithm now has quadratic complexity. Number of digits`first_expr`grows in proportion to the length of the string. Arithmetic operations with it are correspondingly slowed down. This is imperceptible on short lines, but on long lines it will not be good.

``````def phash(base, mod, s):
h= 0
for c in s:
h= (h * base + ord(c)) % mod
return h
base= int(input())
mod= int(input())
s= input()
print(phash(base, mod, s))
``````

understood thanks. Your solution is indeed faster, but still fails on some tests

Came Up2022-01-29 23:34:20

Module (`%`) must be called in a loop. Your algorithm now has quadratic complexity. Number of digits`first_expr`grows in proportion to the length of the string. Arithmetic operations with it are correspondingly slowed down. This is imperceptible on short lines, but on long lines it will not be good.

``````def phash(base, mod, s):
h= 0
for c in s:
h= (h * base + ord(c)) % mod
return h
base= int(input())
mod= int(input())
s= input()
print(phash(base, mod, s))
``````

understood thanks. Your solution is indeed faster, but still fails on some tests

Came Up2022-01-29 23:34:20