Go: отпечаток полинома для сравнения строк

Question

Я хочу реализовать функцию прокручивания ha sh для сравнения строк (Рабин-Карп)

. Для этого я преобразовываю свою входную строку во фрагмент байтов (используя go unicode / utf8) и включите на нем функцию «полиномиальная дактилоскопия».

Например, я ввожу строку qwerty, которая переводится в [113 119 101 114 116 121] Я использую базу 256

rune 121, base 256.0, exponent 0, value 121
rune 116, base 256.0, exponent 1, value 29696
rune 114, base 256.0, exponent 2, value 7471104
rune 101, base 256.0, exponent 3, value 1694498816
rune 119, base 256.0, exponent 4, value 511101108224
rune 113, base 256.0, exponent 5, value 124244813938688

У меня проблемы с понятием «многочленный отпечаток пальца»: быстро, база становится действительно большой, как это может масштабироваться с помощью строкового ввода, который пользователь хочет сопоставить?

В моем случае, это испортилось после 7 символов, потому что функция Go math.Pow использует тип float64

rune 114, base 256.0, exponent 7, value 8214565720323784704
rune 101, base 256.0, exponent 8, value -9223372036854775808
rune 119, base 256.0, exponent 9, value -9223372036854775808
rune 113, base 256.0, exponent 10, value -9223372036854775808

Я чувствую, что использование uint64 просто продвинет немного вперед проблему

Answer 1

Идея функции ha sh заключается в том, что она будет переполнена, но с высокой вероятностью разные строки будут давать разные хэши. Чтобы заставить его работать, вам нужно использовать простые числа для основания и модуля операций. Вы должны использовать некоторую простую базу (больше, чем размер алфавита) и выполнить все операции с модулем некоторого простого числа (как можно большего размера) (простые числа приведут к минимальной вероятности столкновения). Используйте целочисленный тип для этого ха sh. Если ваш алфавит должен быть не менее 256 символов, вы можете использовать uint64, основание 257 и выполнять все операции, например, модуль 10 ¹² + 39