Bizda quyidagi matn bor bo’lsin

Модулярная арифметика

Результат всех вычислений в рамках алгоритма Рабина-Карпа должен браться по модулю Q во избежание появления больших H (т. е. значений хеша) и целочисленных переполнений. Достигается это, правда, ценой увеличения хеш-коллизий, которые ещё называют ложными срабатываниями.
В качестве значения для Q обычно выбирается простое число — настолько большое, насколько это возможно без ущерба для арифметической производительности. Чем меньше значение Q, тем выше вероятность ложных срабатываний.

Этот подход таит в себе потенциальную проблему. Чтобы понять, в чём она заключается, рассмотрим простой фрагмент кода JavaScript:
function hash(pattern, Q) {
const b = 13;
const m = pattern.length; let hash = 0;
for (let i = 0; i < m; i++) {
const charCode = pattern.charCodeAt(i);
hash = (hash + charCode * (b ** (m - i - 1))) % Q;
} return hash % Q;
}
Посмотрите: внутри цикла выполняются два умножения и одно сложение. Это не только неэффективно, но и не позволяет предотвратить переполнение целых чисел: выполняется суммирование больших чисел, а до оператора модуля дело даже не дошло. Эту проблему можно решить методом Хорнера.

Метод Хорнера

Метод Хорнера упрощает процесс вычисления многочлена делением его на одночлены (многочлены 1-й степени).

Применив этот метод, мы можем исключить из предыдущей реализации одно умножение. Таким образом, на каждом шаге цикла у нас остаётся только одно умножение и одно сложение, что позволяет предотвратить переполнение целых чисел:
function hash(pattern, Q) {
const b = 13;
const m = pattern.length;let hash = 0;
for (let i = 0; i < m; i++) {
const charCode = pattern.charCodeAt(i);
hash = (hash * b + charCode) % Q;
} return hash;
}
Этот же подход можно применить для вычисления скользящего хеша за линейное время:
function roll(previousHash, previousPattern, newPattern, base, Q) {
let hashCode = previousHash; // предварительно вычисляем множитель
let multiplier = 1;
for (let i = 1; i < previousPattern.length; i++) {
multiplier *= base;
multiplier %= Q;
} // добавляем модуль для получения неотрицательного хэша
hashCode += Q; hashCode -= (multiplier * previousPattern.charCodeAt(0)) % Q;
hashCode *= base;
hashCode += newPattern.charCodeAt(newPattern.length - 1);
hashCode %= Q; return hashCode;
}