Кормена Строка соответствия Рабина-Карпа

Question

Читаю алгоритм Рабина-Карпа от Введение в алгоритмы по Cormen и т.д.

www.cs.uml.edu/~kdaniels/courses/ALG_503_F08/503_lecture11.ppt

Примечание здесь == используется как мод оператора

Выше ноты на слайде 13, т. Е. Eq 34.2, который прилагается как изображение здесь. В уравнении мы имеем h == (d) powerof ((m-1) (mod q) - это значение цифры «1» в позиции высокого порядка текстового окна с m-значком.

Мой вопрос здесь, что делает автор означает «значение цифры« 1 »в позиции высокого порядка текстового окна с m-значком»?

На слайде 14, как автор получил (7-3.3) .10 + 2 (mod 13), как 8 (mod 13)?

В среднем случае анализа упоминается, что мы можем основывать эвристический анализ на предположении, что уменьшение значений по модулю q действует как случайное отображение от сигмы * к Z. Вот что делает автор по выражению выше?

Answer 1

Ваш второй вопрос - это просто модульная арифметика с номерами -ve. Один из способов подумать об этом - о том, что рабочий мод M вы можете добавлять или вычитать M столько, сколько хотите, поскольку M эквивалентно 0 mod M. Итак, у нас есть (7-3.3) .10 + 2 (mod 13) = -2.10 + 2 = -18 = 13 + 13 - 18 = 8 mod 13

Ваш первый вопрос для меня менее ясен, но позвольте мне подробно его проработать. Когда символ сначала появляется в текстовом окне, он просто добавляется. Затем он перемещается вдоль текстового окна и, наконец, мы хотим удалить всю память из него, чтобы после выхода из текстового окна он не влиял на хэш-значение.

Сначала мы видим символ x и до сих пор добавляем его к значению хэша, поэтому получаем h.d + x. Когда мы видим следующий символ, мы умножаем его на d (и делаем другие вещи, которые я пытаюсь объяснить), а затем добавляем новый символ - скажем y. Итак, мы получаем ... + x * d + y. Следующий шаг дает нам ... + x * d * d + y * d + z. Когда мы как раз собираемся избавиться от символа, мы имеем хэш-значение x * d^(m-1) + ...., где .... зависит только от символов после x. Таким образом, мы можем удалить влияние x на хэш-значение, вычитая x * d^(m-1) до умножения на d.