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[0]) * base + ord(s[1])
for i in range(2, len(s)):
first_expr= first_expr * base + ord(s[i])
print(first_expr % mod)
# 123 |
# 100003 |=> 6080
# hash |
How can I speed up this solution?
-
Answer # 1
Module (
%
) must be called in a loop. Your algorithm now has quadratic complexity. Number of digitsfirst_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 -
Answer # 2
Module (
%
) must be called in a loop. Your algorithm now has quadratic complexity. Number of digitsfirst_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
- python : Bot on aiogram does not see the answer to someone else's message
- How to translate into a normal format -a date from numbers. Python
- Program for finding synonyms of Russian words python
- javascript : How to pass value of js variables to python(eel)?
- python : How to create a window in the game for example (dota2)
- python : Sending a file using telegramAPI
- python : Input() constraint (int, float)
- Authorization key before running Python script
- python : Why does list.remove() incorrectly remove elements in a loop?
Give a link to the testing system.
Stanislav Volodarskiy2022-01-30 07:40:57