Строка Рабина-Карпа элементарных числовых обозначений

Question

Я читаю об алгоритмах String во введении к алгоритмам Cormen и т. Д.

Далее следует текст о некоторых элементарных теоретических обозначениях.

Примечание. В приведенном ниже тексте ссылка == является эквивалентной по модулю.

Учитывая четко определенное представление об остатке одного целого числа при делении на другое, удобно предоставить специальную запись для обозначения равенства остатков. Если (a mod n) = (b mod n), мы пишем a == b (mod n) и говорим, что a эквивалентно b по модулю n. Другими словами, a == b (mod n), если a и b имеют одинаковый остаток при делении на n. Эквивалентно, a == b (mod n) тогда и только тогда, когда n | (б - а). Например, 61 == 6 (мод 11). Также -13 == 22 == 2 == (мод 5).

Целые числа можно разделить на n классов эквивалентности в соответствии с их остатками по модулю n. Класс эквивалентности по модулю n, содержащий целое число a, является

[a]n = {a + kn: k Z} .

Например, [3]7 = {.,, -11, -4, 3, 10, 17, .,.}; другие обозначения для этого набора - [-4]7 и [10]7.

Запись a принадлежит [b]n - это то же самое, что запись a == b (mod n). Множество всех таких классов эквивалентности

Zn = {[a]n: 0 <= a <= n - 1}.----------> Уравнение 1

Мой вопрос в приведенном выше тексте: в уравнении 1 упоминается, что "а" должно быть между 0 и n-1, но в примере оно задается как -4, а не между 0 и 6, почему?

В дополнение к вышесказанному упоминается, что для алгоритма Рабина-Карпа мы используем эквивалентность двух чисел по модулю третьего числа? Что это значит?

Answer 1

Это не вопрос программирования, но не берите в голову...

упомянуто, что "a" должно быть между 0 и n-1, но в примере это дается как -4, а не между 0 и 6, почему?

Потому что [-4]n - это тот же класс эквивалентности, что и [x]n для некоторого x, такого что 0 <= x

В дополнение к вышесказанному упоминается, что для алгоритма Рабина-Карпа мы используем эквивалентность двух чисел по модулю третьего числа? Что это значит?

Алгоритм Рабина-Карпа требует, чтобы вы вычислили значение хеша для искомой подстроки. При хешировании важно использовать хеш-функцию, которая использует весь доступный домен даже для довольно маленьких строк. Если ваш хэш представляет собой 32-разрядное целое число, и вы просто складываете последовательные значения Юникода вместе, ваш хэш обычно будет довольно маленьким, что приведет к множеству коллизий.

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

Answer 2

Я постараюсь подтолкнуть вас в правильном направлении, хотя дело не в программировании.

Пример с -4 в нем является примером класса эквивалентности, который представляет собой набор всех чисел, эквивалентных данному числу. Таким образом, в [3]7 все числа эквивалентны (по модулю 7) 3, и это включает в себя -4, а также 17 и 710 и бесконечность других.

Вы также можете назвать тот же класс [10]7, потому что каждое число, которое эквивалентно (по модулю 7) 3, в то же время эквивалентно (по модулю 7) 10.

Последнее определение дает набор всех различных классов эквивалентности и утверждает, что по модулю 7 их ровно 7, и они могут быть получены числами от 0 до 6. Вы также можете сказать,

Zn = {[a]n : n <= a < 2 * n}

и значение останется прежним, поскольку [0]7 - это то же самое, что и [7]7, а [6]7 - это то же самое, что и [13]7.