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

Question

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

Ниже приведен текст о некоторых теоретических обозначениях элементарных чисел.

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

Учитывая четко определенное понятие остатка одного целого числа при делении на другое, удобно предусмотреть специальную запись для обозначения равенства остатков.Если (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 == (mod 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

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

Пример с -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.

Answer 2

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

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

Потому что [-4] n - это тот же класс эквивалентности, что и [x] n для некоторого x, такого что 0 <= x <n. Таким образом, уравнение 1 использует тот факт, чтобы «согласовать» определение и сделать все возможности различными. </p>

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

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

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