Алгоритм Карпа Рабина

Question

Я реализую алгоритм сопоставления подстрок karp-rabin. Моя реализация работает нормально, когда я вызываю метод hash_string() для подстрок, но терпит неудачу, когда я реализую скользящий хэш. Моя переменная хэш продолжает расти, и я не могу понять, почему.

def hash_string(string, base):
    power = len(string) - 1
    hash_value = 0
    for i in range(power, -1, -1):
        hash_value += (ord(string[i]) * (base ** power))
    return hash_value

def karp_rabin(string, substring):
    substrhash = hash_string(substring, 256)
    rolling_hash_val = hash_string(string[0:len(substring)], 256)
    for i in range(len(string) - len(substring) + 1):
        if substrhash == rolling_hash_val and string[i:i+len(substring)] == substring:
            return i
        if i < len(string) - len(substring):
            print rolling_hash_val
            print (ord(string[i]) * (256 ** (len(substring) - 1))) * 256
            rolling_hash_val = (rolling_hash_val - (ord(string[i]) * (256 ** (len(substring) - 1)))) * 256 + ord(string[i + len(substring)])

print karp_rabin('ababababaababab', 'aab')

Более конкретно, проблема возникает здесь:

rolling_hash_val = (rolling_hash_val - (ord(string[i]) * (256 ** (len(substring) - 1)))) * 256 + ord(string[i + len(substring)])

Значение хеш-функции прокатки увеличивается на порядки, даже если длина подстроки остается неизменной. Правильно ли реализована эта скользящая реализация хеша?

Answer 1

Скользящие хеши обычно делаются по модулю арифметики. Я имею в виду, что там происходит все виды сложения, умножения и возведения в степень - если это не по модулю n (для некоторых n), да, дела будут расти.

(Между прочим, не поддавайтесь искушению просто обновить хеш с последующим модулем. С целыми числами нормального размера это не очень хорошая идея. Используйте фактическое модульное возведение в степень.)