используя хитрый прием, чтобы найти строки, которые вероятно равны.
Определение «хеш-чисел» для строк может облегчить сравнение за счет точности.
Мотивация
Предположим, у нас есть очень длинная строка M и строка пароля p, и мы хотим подсчитать, сколько раз пароль появляется в M.
наивный алгоритм: перейти к каждому символу в M и сформировать строку с последующими символами, проверяя, равна ли сформированная подстрока коду доступа. Время выполнения, естественно, O (n²).
Чтобы сделать это за O(n) (вроде бы), мы используем хеширование.
Алгоритм
Мы определяем хеш-номер строки p как (p[0]*A^n+p[1]*A^n-1…+p[n-1]*A⁰) по модулю B, где p[ind] — это инд-ый символ и A, B — произвольные числа.
Естественно, две одинаковые строки будут иметь общий хеш-номер, и если две строки имеют разные номера, они тоже будут различаться. Однако может случиться так, что две разные строки имеют общий хеш-номер, и это просто потому, что количество возможных чисел всегда будет меньше, чем количество строк.
Быстрый способ вычисления хеш-чисел для подстрок
Мы можем использовать мощь массивов префиксов для эффективного вычисления хэш-чисел для любой подстроки A.
По сути, мы храним в h[i] хеш-номер для M[0…i], что можно сделать с помощью этой рекурсии:
- h[0]=M[0]
- h[j] = (h[j-1]A+S[j])%B, для j›0
Однако этого недостаточно, чтобы вычислить хеш-число для произвольного диапазона M[x…y], для этого нужен еще один массив k, где k[x]=(A^x)%B.
Теперь M[x…y] просто: (h[y]−h[x−1]*k[y−x+1]) %B.
Вернемся к исходной проблеме
Итак, теперь, когда у нас есть эффективный способ вычисления хеш-чисел, как это упрощает задачу? Что ж, мы можем выполнить итерацию M в режиме скользящего окна, чтобы собрать все подстроки с той же длиной и значением хеш-функции, что и p. Получив эти строки, мы можем проверить, действительно ли они равны p.
Это вероятно уменьшает время работы алгоритма, поскольку вероятность того, что две разные строки имеют одинаковый хеш-код, становится очень малой по мере увеличения длины B.
