0

Вычисляю полиноминальный хеш на строке s. Мое решение (метод Горнера):

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   |

Как можно ускорить это решение?

1
  • Дайте ссылку на тестирующую систему. 30 янв 2022 в 7:40

1 ответ 1

2

Модуль (%) надо вызывать в цикле. У вашего алгоритма сейчас квадратичная сложность. Число цифр first_expr растёт пропорционально длине строки. Соответственно замедляются арифметические операции с ним. Это незаметно на коротких строках, но на длинных будет не хорошо.

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))
1
  • понял, спасибо. Ваше решение действительно быстрее, но все равно на некоторых тестах не проходит
    – Came Up
    29 янв 2022 в 23:34

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.