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 you have read our privacy policy.

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